Page 261 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes The output is given below:

Self Assessment

Fill in the blanks:
1. Linear search is the basic searching algorithm, also called as .......................... search.
2. The complexity of this type of search is .......................... because, in the worst case all items
in the search space will be examined.
3. The .......................... case performance scenario for a linear search is that it needs to loop
through the entire collection.
4. The function will return the index into the array that the value was found at, or ..........................
if the value wasn’t found.

5. In C, arrays of length N have indices numbered 0 through ..........................
6. Our sequential search function for linked lists will take two arguments: a ..........................
to the first element in the list and the value for which we are searching.

7. To employ linear search, you must first know where the data collection begins and the
.......................... of the area to search.
8. Because there are faster ways of searching a memory space, the linear search is sometimes
referred to as a ..........................

14.2 Binary Search

When it is known that a data set is in sorted order it is possible to drastically increase the speed
of a search operation in most cases. An array-based binary search selects the median (middle)
element in the array and compares its value to that of the target value. Because the array is
known to be sorted, if the target value is less than the middle value then the target must be in the
first half of the array. Likewise if the value of the target item is greater than that of the middle
value in the array, it is known that the target lies in the second half of the array. In either case we
can, in effect, “throw out” one half of the search space with only one comparison.
Now, knowing that the target must be in one half of the array or the other, the binary search
examines the median value of the half in which the target must reside. The algorithm thus
narrows the search area by half at each step until it has either found the target data or the search
fails.

254 LOVELY PROFESSIONAL UNIVERSITY