To implement binary search recursively in Java, we'll follow these steps:
- Using the pseudocode shown in Snippet 2.5, implement a recursive binary search function.
- Provide another method with a signature that only contains the search item and the sorted array as input. This method will then call the recursive function with appropriate values as follows:
public boolean binarySearch(int x, int[] sortedNumbers)
Output
The following code shows the additional method making the initial call and the recursive function as follows:
public boolean binarySearch(int x, int[] sortedNumbers, int start,
int end) {
if (start <= end) {
int mid = (end - start) / 2 + start;
if (sortedNumbers[mid] == x) return true;
if (sortedNumbers[mid] > x)
return binarySearch(x, sortedNumbers, start, mid - 1);
return binarySearch(x, sortedNumbers, mid + 1, end);
}
return false;}
Snippet 2.6: Recursive binary search. Source class name: BinarySearchRecursive
Recursion is an essential tool for any developer and we'll make use of it in many parts in this book. In this section, we implemented an example for binary searching. In the next section, we shall look at how partitioning works in the quicksort algorithm.