38  Binary Search

38.3 Divide and Conquer

When faced with a complex problem, one of the most effective strategies is often to break it down into smaller, more manageable parts. This is the essence of the ‘divide and conquer’ strategy. We divide the problem into several sub-problems that are similar to the original but smaller in size. We conquer the sub-problems by solving them recursively. Finally, we combine the solutions of the sub-problems to solve the original problem.

The divide and conquer strategy is especially effective when the sub-problems can be solved independently and the solutions can be combined efficiently. In the context of searching, we can apply this strategy by dividing the search space into smaller parts and searching each part separately. If we can eliminate large parts of the search space at each step, we can find the target value much faster.

Let’s see how we can apply this to Search, and our original problem of looking for books in a library!

The journey to our favorite author’s book in the library hasn’t been as fast as we initially desired. Checking every book, or even every other book, can still be cumbersome in a large library.

So, let’s revisit our library metaphor and imagine a different scenario. Now, you have an idea. Instead of searching from ‘A’ to ‘Z’ linearly, you begin your search in the middle of the library, around ‘M.’ If Atwood falls in the latter half, ignore everything from ‘A to L.’ And voila! Half the library gets eliminated instantly.

But in order for this to work, we need to make an assumption – the library is sorted alphabetically. If it isn’t, we’ll have to sort it first, which is a whole other problem. But if it is, we can apply the divide and conquer strategy to our search.

Now let’s put it into practice by creating a new method called drasticallyFasterSearch:

public int drasticallyFasterSearch(int[] arr, int left, int right, int key) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == key)
        return mid;
    else if (arr[mid] > key)
        return optimizedLinearSearch(
          java.utils.Arrays.copyOfRange(arr, 0, mid - 1), 0, mid - 1, key
        );
    else
        return optimizedLinearSearch(
          java.utils.Arrays.copyOfRange(arr, mid + 1, right), 0, right - mid - 1, key
        );
}

The drasticallyFasterSearch method is a hybrid function that combines our earlier optimizedLinearSearch to our new Divide and Conquer strategy. The method takes four parameters: arr, which is the array to be searched, left, which is the leftmost index of the subarray to be searched, right, which is the rightmost index of the subarray to be searched, and key, which is the value to be found.

The method has three cases:

  • The base case: If the element at the middle of the subarray (arr[mid]) is equal to key, it means that the key has been found at that position. In this case, the method returns mid to indicate the location of the key in the array.
  • The recursive case 1: If the element at the middle of the subarray (arr[mid]) is greater than key, it means that the key must be in the left half of the subarray. In this case, the method makes a recursive call to optimizedLinearSearch with a smaller subarray (arr[0] to arr[mid-1]). This way, the method eliminates half of the elements from the search space and then applies optimized linear search on the remaining elements.
  • The recursive case 2: If the element at the middle of the subarray (arr[mid]) is less than key, it means that the key must be in the right half of the subarray. In this case, the method makes a recursive call to optimizedLinearSearch with a smaller subarray (arr[mid+1] to arr[right]). This way, the method eliminates half of the elements from the search space and then applies optimized linear search on the remaining elements.

The data flows through the recursive calls via the parameters and return values. The parameters (arr, left, right, and key) help in propagating information forward through the recursive calls until reaching one of the base cases. The return values (mid, -1, left, or right) relay information back from the base case to the original caller.

Let’s illustrate this with an example: Suppose we want to search for 5 in the sorted array {1, 2, 3, 4, 5} using drasticallyFasterSearch. We start by calling drasticallyFasterSearch(arr, 0, 4, 5), where arr is {1, 2, 3, 4, 5}, left is 0, right is 4, and key is 5. The recursive tree will look like this:

drasticallyFasterSearch(arr, 0, 4, 5)
|____ drasticallyFasterSearch(arr, 3, 4, 5)
      |____ optimizedLinearSearch(arr[3..4], 0 ,1 ,5) => returns 1

At each recursive call, we check if we have reached one of the base cases. If not, we make another recursive call with a smaller subarray. When we reach optimizedLinearSearch(arr[3..4], 0 ,1 ,5), we find that arr[4] is equal to key, so we return 1. This value is then added to left (which is 3) and passed back up the call stack until it reaches the original caller. So, drasticallyFasterSearch(arr, 0 ,4 ,5) returns (3 + 1) = 4, indicating that 5 is found at index 4 in the array.

38.4 Even faster drasticallyFasterSearch

Building on our previous exploration, we can see a pattern emerging. We are using our drasticallyFasterSearch to divide our problem, but when it comes to conquering, we are falling back to optimizedLinearSearch. This means we are not fully utilizing the strength of our divide and conquer approach. We have an opportunity for optimization here: what if, instead of resorting to linear search, we applied the same divide and conquer strategy again? This observation leads us to the Binary Search algorithm, a more efficient way to search sorted arrays, which would look like this:

public int drasticallyFasterSearch(int[] arr, int left, int right, int key) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == key)
        return mid;
    else if (arr[mid] > key)
        return drasticallyFasterSearch(
          java.utils.Arrays.copyOfRange(arr, 0, mid - 1), 0, mid - 1, key
        );
    else
        return drasticallyFasterSearch(
          java.utils.Arrays.copyOfRange(arr, mid + 1, right), 0, right - mid - 1, key
        );
}

But would this actually work? We need to use what we learnt about writing recursive functions to find out - what are the base cases? What are the recursive cases? How does the data flow through the recursive calls?

The analysis of the drasticallyFasterSearch method is left as an exercise for the reader.

One fatal flaw with the drasticallyFasterSearch function, as it is currently written, is that there is only one base case - when we find the element and return the mid index. If the element we’re searching for is not in the array, the function will enter into an infinite loop because it lacks a base case to handle this situation.

So, we need an additional base case to handle the scenario where the element is not in the array. This needs to be a condition that detects if we’ve run out of elements in the array that we haven’t yet searched.

This is where the skill of tracing recursive functions comes in handy. We can trace the function to see what happens when we run out of elements to search. Let’s trace the function for the example we used earlier: searching for 5 in the sorted array {1, 2, 3, 4, 5} results in the following recursive call sequence:

drasticallyFasterSearch(arr, 0, 4, 5)
|____ drasticallyFasterSearch(arr, 3, 4, 5)
      |____ drasticallyFasterSearch(arr, 4, 4, 5) 
            => returns 4

But what happens if the number we’re searching for isn’t in the array? What if we’re looking for 6 in the same array?

drasticallyFasterSearch(arr, 0, 4, 6)
|____ drasticallyFasterSearch(arr, 3, 4, 6)
      |____ drasticallyFasterSearch(arr, 4, 4, 6)
            |____ drasticallyFasterSearch(arr, 5, 4, 6)

This last recursive call, drasticallyFasterSearch(arr, 5, 4, 6) is problematic because it makes no sense to start at an index higher than our end index. This means we’ve exhausted all potential elements in our search.

This suggests that we need an additional base case to handle when our left index exceeds our right index. This makes sense because there is no reason for left to be on the right of right! So, we should modify our search method to be:

public int drasticallyFasterSearch(int[] arr, int left, int right, int key) {
    if (right < left)
        return -1;

    int mid = left + (right - left) / 2;

    if (arr[mid] == key)
        return mid;
    else if (arr[mid] > key)
        return drasticallyFasterSearch(
          java.utils.Arrays.copyOfRange(arr, 0, mid - 1), 0, mid - 1, key
        );
    else
        return drasticallyFasterSearch(
          java.utils.Arrays.copyOfRange(arr, mid + 1, right), 0, right - mid - 1, key
        );
}

Now, we can see that when right becomes less than left, the function will correctly return -1, signaling that our intended key isn’t present. Note that in the case where left equals right, we still want to check the arr[mid], so right < left, not right <= left, is our base case.

As we apply the divide and conquer methodology here, our drasticallyFasterSearch method is now a working implementation of the Binary Search algorithm. In each recursive call, we cut our search space in half, drastically reducing the number of elements searched. For a list of length n, in the worst-case, we’ll make roughly log(n) recursive calls, scaling our runtime far better than a linear search would.

Indeed, this is a powerful tool for searching sorted data. By fully utilizing divide and conquer, we’ve been able to drastically speed up our search. This emphasizes the importance of understanding the fundamentals of recursion and problem decompositions as key building blocks in algorithm and data structure design.

As the reader (or student!) progresses, they may find more elegant ways to implement this algorithm, or variations of it, which solve complex problems in different contexts. Here is a variation of the this dearch algorithm that is more efficient and doesn’t require copying the array at each recursive call:

public int drasticallyFasterSearch(int[] arr, int left, int right, int key) {
    if (right >= left) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] > key)
            return drasticallyFasterSearch(arr, left, mid - 1, key);
        else
            return drasticallyFasterSearch(arr, mid + 1, right, key);
    } else {
        return -1;
    }
}