Binary search was introduced in Searching Arrays. For binary search to work, the elements in the array must be in increasing order. The binary search first compares the key with the element in the middle of the array. Consider the following three cases:
- Case 1: If the key is less than the middle element, recursively search for the key in the first half of the array.
- Case 2: If the key is equal to the middle element, the search ends with a match.
- Case 3: If the key is greater than the middle element, recursively search for the key in the second half of the array.
Case 1 and Case 3 reduce the search to a smaller list. Case 2 is a base case when there is a match. Another base case is that the search is exhausted without a match. The code below gives a clear, simple solution for the binary search problem using recursion.
The first method finds a key in the whole list. The second method finds a key in the list with index from low to high.
The first binarySearch method passes the initial array with low = 0 and high = list.length - 1 to the second binarySearch method. The second method is invoked recursively to find the key in an ever-shrinking subarray.
Top comments (0)