This book is now obsolete Please use CSAwesome instead.
13.3. Binary Search¶
A binary search can only be used if the data is sorted.
It compares a target value to the value in the middle of a range of indices. If the value isn’t found it looks again in either the left or right half of the current range. Each time through the loop it eliminates half the values in the search area until either the value is found or there is no more data to look at. Click on this Binary Search Animation to see how it works.
Binary search calculates the middle index as
left + right / 2 where left starts out at 0 and right starts out at the array length - 1 (the index of the last element). Remember that integer division gives an integer result so 2.5 becomes 2. It compares the value at the middle index with the target value (the value you are searching for). If the target value is less than the value at the middle it sets right to middle minus one. If the target value is greater than the value at the middle it sets left to middle plus one. Otherwise the values match and it returns the middle index. It also stops when left is greater than right which indicates that the value wasn’t found and it returns -1.
The code for
binarySearch below is from the AP CS A course description.
To see this executing using the Java Visualizer click on the following link: BinarySearch Ex