Binary Search

Binary Search

There is quite obviously no way to speed up a search, unless more information is available about the searched data. It is well known that a search can be made much more effective, if the data are ordered. Imagine, for example, a telephone directory in which the names were not alphabetically listed. It would be utterly useless. We shall therefore present an algorithm which makes use of the knowledge that a is ordered of the condition

The key idea is to inspect an element picked at random, say am, and to compare it with the search argument x. If it is equal to x, the search terminates; if it is less than x, we infer that all elements with indices less or equal to m can be eliminated from further searches; and if it is greater than x, all with index greater or equal to m can be eliminated. This results in the following algorithm called binary search; it uses two index variables L and R marking the left and at the right end of the section of a in which an element may still be found.



The terminating condition is L
≥ R. Is it guaranteed to be reached? In order to establish this guarantee, we must show that under all circumstances the difference R-L is diminished in each step. L < R holds at the beginning of each step. The arithmetic mean m then satisfies L
≤
m < R. Hence, the difference is indeed
diminished by either assigning m+1 to L (increasing L) or m to R (decreasing R), and the repetition terminates with L = R. However, the invariant and L = R do not yet establish a match. Certainly, if R = N, no match exists. Otherwise we must take into consideration that the element a[R] had never been compared. Hence, an additional test for equality a[R] = x is necessary. In contrast to the first solution, this algorithm -- like linear search -- finds the matching element with the least index.