next up previous contents index Search
Next: Source Code Up: 0.2.2 Binary Search Previous: 0.2.2 Binary Search Analysis

A binary search on an array is O(log2 n) because at each test you can ``throw out'' one half of the search space. If we assume n, the number of items to search, is a power of two (i.e. n = 2x) then, given that n is cut in half at each comparison, the most comparisons needed to find a single item in n is x. It is noteworthy that for very small arrays a linear search     can prove faster than a binary search. However as the size of the array to be searched increases the binary search is the clear victor in terms of number of comparisons and therefore overall speed.

Still, the binary search has some drawbacks. First of all, it requires that the data to be searched be in sorted order. If there is even one element out of order in the data being searched it can throw off the entire process. When presented with a set of unsorted data the efficient programmer must decide whether to sort the data and apply a binary search or simply apply the less-efficient linear search. Even the best sorting algorithm is a complicated process. Is the cost of sorting the data is worth the increase in search speed gained with the binary search? If you are searching only once, it is probably better to do a linear search in most cases.

Once the data is sorted it can also prove very expensive to add or delete items. In a sorted array, for instance, such operations require a ripple-shift   of array elements to open or close a ``hole'' in the array. This is an expensive operation as it requires, in worst case, log2 ncomparisons and n item moves.

The binary search assumes easy random-access to the data space it is searching. An array is the data structure that is most often used because it is easy to jump from one index to another in an array. It is difficult, on the other hand, to efficiently compute the midpoint of a linked list     and then traverse there inexpensively. The binary search tree data structure and algorithm, which we discussed later,     attempt to solve these array-based binary search weaknesses.

Scott Gasch