Binary search algorithm & trace
Binary search efficiently searches an array to find a given key. The array must already be sorted for the algorithm to work.
For the example traces below, the algorithm returns the position of key in arr or -1 if key is not in arr. A more sophisticated return value when key is not found is featured below in the Binary search with insertion point return section.
Example 1
Step 1
arr -> [11 24 35 36 71 75 78 79 86 86]
0 1 2 3 4 5 6 7 8 9
key: 35
low: 0
high: 9
arr and key are parameters. low and high (sometimes called start and end) are indexes that represent the bounds of the part of the array that remains to be searched. The initial values of low and high are 0 and arr.length - 1, respectively.
Step 2
The value of mid is the average of low and high, calculated using integer division (drop any decimal portion).
mid: 4
key (35) is less than arr[mid] (71). If key is in arr, it must be to the left of mid. The value of high is updated to mid - 1. The value of low remains the same.
arr -> [11 24 35 36 71 75 78 79 86 86]
0 1 2 3 4 5 6 7 8 9
key: 35
low: 0
high: 3
Step 4
mid: 1
key (35) is greater than arr[mid] (24). low is updated to mid + 1.
arr -> [11 24 35 36 71 75 78 79 86 86]
0 1 2 3 4 5 6 7 8 9
key: 35
low: 2
high: 3
Step 5
mid: 2
key (35) is equal to arr[mid]. The algorithm stops and returns mid (2), which is the position of key in arr.
Example 2
arr -> [11 24 35 36 71 75 78 79 86 86]
0 1 2 3 4 5 6 7 8 9
key: 86
low |
high |
mid |
|---|---|---|
0 |
9 |
4 |
5 |
9 |
7 |
8 |
9 |
8 |
The algorithm returns 8, a position of 86 in arr.
In this example, the algorithm happened to find the first 86 in the array. This is not always the case. If asked what is returned when executing binary search on an array with more than 1 copy of key, trace the algorithm to find the specific index returned.
Example 3
arr -> [11 24 35 36 71 75 78 79 86 86]
0 1 2 3 4 5 6 7 8 9
key: 40
low |
high |
mid |
|---|---|---|
0 |
9 |
4 |
0 |
3 |
1 |
2 |
3 |
2 |
3 |
3 |
3 |
4 |
3 |
not computed |
On the last step, low is greater than high. This means there are 0 elements in the part of the array left to search, so key is not in arr.
On the step above, low == high. We cannot stop just because low == high. There is still 1 element to check.
Binary search implementations
Recursive binary search
private static int binarySearch(int[] arr, int key, int low, int high)
{
if (low > high)
return -1;
int mid = (low + high) / 2;
if (key < arr[mid])
return binarySearch(arr, key, low, mid - 1);
else if (key > arr[mid])
return binarySearch(arr, key, mid + 1, high);
else
return mid;
}
public static int binarySearch(int[] arr, int key)
{
return binarySearch(arr, key, 0, arr.length - 1);
}
Binary search is easy to implement recursively. The private method takes the parameters necessary to constrain the search to part of the array. The public method takes the parameters appropriate for a search method.
As mentioned above, the precondition for binary search is that the array is sorted.
Iterative binary search
public static int binarySearch(int[] arr, int key)
{
int low = 0;
int high = arr.length - 1;
while(low <= high)
{
int mid = (low + high) / 2;
if (key < arr[mid])
high = mid - 1;
else if (key > arr[mid])
low = mid + 1;
else
return mid;
}
return -1;
}
The iterative implementation of binary search creates low and high as local variables instead of as parameters.
Binary search with insertion point return
public static int binarySearch(int[] arr, int key, int low, int high)
{
if (low > high)
return -low - 1;
int mid = (low + high) / 2;
int result = key - arr[mid];
if (result < 0)
return binarySearch(arr, key, low, mid - 1);
else if (result > 0)
return binarySearch(arr, key, mid + 1, high);
else
return mid;
}
The version of binary search above is identical to the original except that it returns a more sophisticated value when key is not found in arr. A simple version of binary search returns -1 when key is not found in arr. Since arr is sorted, there is additional information available when key is not found. Specifically, the algorithm knows the position at which key would need to be inserted into arr to maintain the sorted order. This position is known as the insertion point.
If low > high (the base case) the insertion point is low. The method above returns -low - 1. This allows for quick examination of the return value to determine if key was found. (A negative return value indicates that key was not found.) It also allows for quick convertion to the actual insertion point if desired.
Problem #10 in the 2014 AP CS A Course Description sample multiple choice makes use of a variant of the above. The variant in the problem returns the actual insertion point (low) rather than a modified version of it (-low - 1).
One of my insertion sort variants calls the method above to determine where to insert the element into the sorted part.
Binary search with ArrayList<String>
public static int binarySearch(ArrayList<String> list, String key, int start, int end)
{
if (start > end)
return -start - 1;
else
{
int mid = (start + end) / 2;
int result = key.compareTo(list.get(mid));
if (result < 0)
return binarySearch(list, key, start, mid - 1);
else if (result > 0)
return binarySearch(list, key, mid + 1, end);
else
return mid;
}
}
This is nearly identical to the variant above, except it uses compareTo. The result of the call to compareTo is stored in result to avoid calling compareTo twice.
For more about how to handle compareTo on the AP CS A Exam, see compareTo on the AP CS A Exam.