Previous: 10.2 Improving Search - Sorting the Data
Up: 10 Sorting and Searching
Next: 10.4 An Example - Payroll Data Records
Previous Page: 10.2.3 Insertion Sort
Next Page: 10.4 An Example - Payroll Data Records
Previous: 10.2 Improving Search - Sorting the Data
Up: 10 Sorting and Searching
Next: 10.4 An Example - Payroll Data Records
Previous Page: 10.2.3 Insertion Sort
Next Page: 10.4 An Example - Payroll Data Records
As we saw earlier, the linear search algorithm is simple and convenient for small problems, but if the array is large and/or requires many repeated searches, it makes good sense to have a more efficient algorithm for searching an array. Now that we know how to sort the elements of an array, we can make use of that ordering to make our search more efficient. In this section, we will present and implement the binary search algorithm, a relatively simple and efficient algorithm.
The algorithm is easily explained in terms of searching a dictionary for a word. In a dictionary, words are sorted alphabetically. For simplicity, let us assume there is only one page for all words starting with each letter. Let us assume we wish to search for a word starting with some particular letter.
We open the dictionary at some midway page, let us say a page on which words start with M. If the value of our letter is M, then we have found what we are looking for and the word is on the current page. If the value of our letter is less than M, we know that the word would be found in the first half of the book, i.e. we should search for the word in the pages preceding the current page. If the value of our letter is greater than M, we should search the pages following the current page. In either case, the effective size of the dictionary to be searched is reduced to about half the original size. We repeat the process in the appropriate half, opening to somewhere in the middle of that and checking again. As the process is repeated, the effective size of the dictionary to be searched reduces by about half at each step until the word is found on a current page.
Binary search essentially follows this approach. For example, given a sorted array of items, say:
12, 29, 30, 32, 35, 49suppose we wish to search for the position of an element equal to x. We will search the array which begins at some low index and ends at some high index. In our case the low index of the effective array to be searched is zero and the high index is 5. We can find the approximate midway index by integer division (low + high) / 2, i.e. 2. We compare our value, x with the element at index 2. If they are equal, we have found what we were looking for; the index is 2. Otherwise, ff x is greater then the item at this index, our new effective search array has a low index value of 3 and the high index remains unchanged at 5. If x is less than the element, the new effective search array has a high index of 1 and the low index remains at zero. The process repeats until the item is found, or there are no elements in the effective search array. The terminating condition is found when the low index exceeds the high index. The algorithm is implemented as a function in Figure 10.14.
We use the binsrch() function in an example program which repeatedly searches for numbers input by the user. For each number, it either gives the index where it is found or prints a message if it is not found. An array in sorted form is initialized in the declaration. The code for this driver is shown in Figure 10.15
Sample Session: