1.1 Binary Search |
We have already seen in the previous section how to search in an array by sequentially running through the array and comparing each element with a given key. In worst case, we have to investigate the whole array to find the desired element (or find out that the element is not in the array). If the array consists of n elements, this requires n comparison operations; therefore we call the search algorithm linear in the length of the input array.
There is a better way of searching for an element in an array provided that the array is sorted, i.e., the elements of the array are arranged in some (e.g., ascending) order. Assume that we are looking for the element 13 in the array
We use truncated integer division. |
The following applet illustrates the algorithm.
If you don't see the applet, your Browser does not support Java. Click here, to view a precomputed image. |
// ------------------------------------------------ // i = binarySearch(a, x) // 'i' is the index of 'x' in 'a'. // // Input: // 'a' is not null and sorted in ascending order. // Output: // 'a' remains unchanged. // if 'i' == -1, then 'x' is not in 'a'. // if 'i' != -1, then 'a[i] == x'. // ------------------------------------------------ static int binarySearch(int[] a, int x) { int low = 0; int high = a.length-1; while (low <= high) { // x does not occur in a in any position // less than low or greater than high int mid = (low + high)/2; if (a[mid] == x) return mid; if (x > a[mid]) low = mid+1; else high = mid-1; } // x does not occur in a return -1; }
Since in every iteration the size of the search range (the difference between high and low) is halved, the function needs at most as many comparisons as correspond to the binary logarithm of the length of the array; we call the algorithm logarithmic in the array length. For instance, if the array is 1024=2^{10} elements long, at most 10 iterations are required to find an element or determine that the element is not in the array. Sorted arrays can therefore be searched very quickly compared with arrays that are not sorted.
1.1 Binary Search |