Binary search is an algorithm in which a data structure, such as an array or a list, known to be in sorted order is searched efficiently for a specific value. Since the data structure is known to be sorted the middle element is checked against the value sought. If the value matches, the index of the middle element is returned. If the value does not match, the half of the data structure that could contain the value is searched recursively.
If the value sought is not found, a number indicating where the value should be inserted (to maintain the sorted order) is returned.
On the AP Computer Science Exam, you must recognize the algorithm when it is presented in code. You may be expected to compare the efficiency to sequential search as well as recognize the significant limitation of binary search (that the data structure must be sorted).
The precondition for method binarySearch is: x is sorted in increasing order. The method returns the index of key in x. If key is not in x, the method returns (-(insertion point) – 1) where insertion point is the index at which key would be inserted in x to maintain x in sorted order.
Complete method binarySearch below. You must declare and write a recursive helper method with an appropriate header.
public static int binarySearch(int x, int key)