Algorithms: Binary Search

Posted on: July 26, 2006 at 12:00 AM

Posted on: July 26, 2006 at 12:00 AM

This performance comes at a price - the array must be sorted first. Because sorting isn't a fast operation, it may not be worth the effort to sort when there are only a few searches.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
/** Binary search of sorted array. Negative value on search failure. * The upperbound index is not included in the search. * This is to be consistent with the way Java in general expresses ranges. * The performance is O(log N). * @param sorted Array of sorted values to be searched. * @param first Index of beginning of range. First element is a[first]. * @param upto Last element that is searched is sorted[upto-1]. * @param key Value that is being looked for. * @return Returns index of the first match, or or -insertion_position * -1 if key is not in the array. This value can easily be * transformed into the position to insert it. */ public static int binarySearch(int[] sorted, int first, int upto, int key) { while (first < upto) { int mid = (first + upto) / 2; // Compute mid point. if (key < sorted[mid]) { upto = mid; // repeat search in bottom half. } else if (key > sorted[mid]) { first = mid + 1; // Repeat search in top half. } else { return mid; // Found it. return position } } return -(first + 1); // Failed to find key } |