Step 5 of 6

Recursive binary search

Module 28 searched a sorted array with binary search, in a while loop: look at the middle value, and if it isn't the wanted one, go on in the half where the wanted value would be. "Go on in the half" is the same search on a smaller range, so binary search can also be written recursively.

The range as parameters

The loop kept the range in two variables, low and high. The recursive method gets them as parameters, and the recursive call gets the new range. A greengrocer keeps the prices of the products, in cents, in a sorted array:

public class Main {
    public static void main(String[] args) {
        int[] prices = {45, 80, 120, 199, 250, 310, 475, 520};
        System.out.println(find(prices, 310, 0, prices.length - 1));
        System.out.println(find(prices, 100, 0, prices.length - 1));
    }

    public static int find(int[] sorted, int wanted, int low, int high) {
        if (low > high) {
            return -1;
        }
        int middle = (low + high) / 2;
        System.out.println("  looking between " + low + " and " + high + " at " + sorted[middle]);
        if (sorted[middle] == wanted) {
            return middle;
        }
        if (sorted[middle] < wanted) {
            return find(sorted, wanted, middle + 1, high);
        }
        return find(sorted, wanted, low, middle - 1);
    }
}

Output

  looking between 0 and 7 at 199
  looking between 4 and 7 at 310
5
  looking between 0 and 7 at 199
  looking between 0 and 2 at 80
  looking between 2 and 2 at 120
-1

There are two base cases: an empty range (low > high), where the value isn't in the array, and a middle value that is the wanted one. Every other call searches a range at most half as long, so the calls reach a base case quickly: for an array of a million values, at most 20 looks, as in module 28. The recursion is at most about 20 calls deep, so the call stack is never a problem here.

Each recursive call is return find(...): the method returns whatever the smaller search found, unchanged. The answer is found at the bottom and passed up through every call.

A friendlier method on top

Callers shouldn't have to pass 0 and prices.length - 1 themselves. The usual way is a second method with the same name and fewer parameters, which starts the search on the whole array (two methods with the same name and different parameters are overloads, module 21):

public static int find(int[] sorted, int wanted) {
    return find(sorted, wanted, 0, sorted.length - 1);
}

The extra parameters of the recursive method are then a detail that only this class sees. The third challenge of this step uses the pattern.

Your task

Challenge 1 of 3

A greengrocer's till has the sorted array of prices, in cents. Write the recursive method findPrice(int[] prices, int price, int low, int high), which returns the index of price in prices between the indexes low and high, or -1 if it isn't there. Do it without a loop: binary search, as in this step. The check runs:

int[] prices = {35, 60, 99, 140, 185, 230, 299, 365, 420};
System.out.println(findPrice(prices, 299, 0, prices.length - 1));
System.out.println(findPrice(prices, 100, 0, prices.length - 1));

and expects:

6
-1

Challenge 2

An auction keeps its bids in a sorted array. When a new bid comes in, where does it go? Write the recursive method placeFor(int[] bids, int bid, int low, int high), which returns the index where bid belongs between low and high: the index of an equal bid if there is one, and otherwise the index of the first bid that's larger (or high + 1 if no bid is larger). That's the binary search of this step with one change: when the range is empty, return low instead of -1. When the range is empty, low has moved past every smaller bid. The check runs:

int[] bids = {100, 150, 220, 300, 410};
System.out.println(placeFor(bids, 220, 0, bids.length - 1));
System.out.println(placeFor(bids, 200, 0, bids.length - 1));
System.out.println(placeFor(bids, 500, 0, bids.length - 1));

and expects:

2
2
5

Challenge 3

A school's lost-and-found keeps the names on its labels in a sorted array, in alphabetical order (as compareTo orders them, module 38). Write two methods named findLabel:

findLabel(String[] labels, String name, int low, int high): the recursive binary search between low and high, returning the index of name, or -1. Strings are compared with compareTo: name.compareTo(labels[middle]) is 0 when they are equal, below 0 when name comes first, and above 0 when it comes after.
findLabel(String[] labels, String name): searches the whole array, by calling the first one.

The check calls only the second one. It runs:

String[] labels = {"Aino", "Bilal", "Chen", "Dara", "Emil", "Freya", "Gus"};
System.out.println(findLabel(labels, "Emil"));
System.out.println(findLabel(labels, "Bo"));

and expects:

4
-1

Previous: When recursion goes wrong Next: Divide and conquer: merge sort