|
|
|
|
|
|
|
middle = (first + last) / 2; |
|
|
|
|
|
|
|
|
explains why the function precondition restricts the value of length to INT_MAX/2. If the item being searched for happens to reside in the last position of the list (for example, when item equals 400 in our sample list), then first + last equals length + length. If length is greater than INT_MAX/2, the sum length + length would produce an integer overflow. |
|
|
|
|
|
|
|
|
Notice in the table that whether we searched for 106, 400, or 406, the loop never executed more than four times. It never executes more than four times in a list of 11 components because the list is being cut in half each time through the loop. The table below compares a sequential search and a binary search in terms of the average number of iterations needed to find an item. |
|
|
|
|
| | Average Number of Iterations |
| | Sequential Search | Binary Search | | | | | | | | | | | | |
|
|
|
|
|
|
If the binary search is so much faster, why not use it all the time? It certainly is faster in terms of the number of times through the loop, but more computations are performed within the binary search loop than in the other search algorithms. This means that if the number of components in the list is small (say, less than 20), the sequential search algorithms are faster because they do less work at each iteration. As the number of components in the list increases, the binary search algorithm becomes relatively more efficient. Remember, however, that the binary search requires the list to be sorted, and sorting itself takes time. Keep three factors in mind when you are deciding which search algorithm to use: |
|
|
|
|
|
|
|
|
1. The length of the list to be searched |
|
|
|
|
|
|
|
|
2. Whether or not the list already is ordered |
|
|
|
|
|
|
|
|
3. The number of times the list is to be searched |
|
|
|
|
|