Introduction to Divide and Conquer with Binary Search

This lesson introduces the divide and conquer technique of solving a problem using binary search in a sorted array.

We'll cover the following

Divide and conquer method

Divide and conquer is an algorithmic paradigm in which the problem is repeatedly divided into subproblems until we reach a point where each problem is similar and atomic, i.e., can’t be further divided. At this point, we start solving these atomic problems and combining (merging) the solutions together. Therefore, divide and donquer solutions have the following three steps:

  1. Divide
  2. Conquer
  3. Merge

Let’s take an example to grasp this concept better.

Example: Binary search

Consider a sorted array arr, of n integers, and we are required to find if a particular integer value exists in the given array or not.

%0 node_1 2 node_2 4 node_3 7 node_1551329432742 8 node_1551329492659 10 node_1551329543950 13 node_1551329479805 14 node_1551329567033 17 node_1551329474396 31 node_1551329514663 94 node_1551332277696 99
A sorted array of 11 integers

Now, we could go about searching the array in a linear manner, starting from the 0th index and checking the value at each index as we move towards the 10th index. However, a fascinating property of sorted arrays is that regardless of the element we are looking at, we can be sure that the next element has either a value greater than or equal to the current element and the previous element has either a value lesser than or equal to the current element.

In sorted arrays, the value at index i+1 is greater than or equal to the element at index i, and the value at index i-1 is lesser than or equal to the element at index i.

How can we use this property? If we are looking for a key k in the array (considering the array is sorted in ascending order) at any particular index i, there are three possibilities:

  1. arr[i] == k, when the key is found
  2. arr[i] < k, where the key must exist in the right subarray
  3. arr[i] > k, where the key must exist in the left subarray

Time complexity

If we start in the middle of the array, either we are lucky and the element matches or we discard half of the array. In the worst case, we repeatedly discard half of the sub-arrays from the previous step until the array can no longer be subdivided, i.e., it is of size 1. An array of size n can be divided into halves lgnlg n times until we reach a subarray of size 1. Hence, the time complexity of finding an element in a sorted array using this technique is O(lg n)O(lg \ n).

Visualization

Code

class DivideAndConquer {
 
 public static int BinarySearch(int arr[], int left, int right, int key) {
  
  if (right >= left) {
   
   int MidElement = left + (right - left) / 2;
   if (arr[MidElement] == key) // If the required element is found at the middle index
    return MidElement;
   if (key < arr[MidElement]) // If the required element is smaller than the element at the middle index  It can only be present in the left subarray 
    return BinarySearch(arr, left, MidElement - 1, key);
   return BinarySearch(arr, MidElement + 1, right, key); // else, it would be present in the right subarray  
  }
  return -1; // Element not found, and the array can not be further divided.  
 }
public static void main(String args[]) {
 
 int arr[] = { 3, 5, 7, 15, 25 }; 
 int key = 7; // to find, feel free to change this
 int result = BinarySearch(arr, 0, arr.length - 1, key);
 if (result != -1)
  System.out.println("Key " + "\"" + key + "\" found at index = " + result);
 else
  System.out.println("Key " + "\"" + key + "\"not found!");
 key = 0; // Trying for a different value
 result = BinarySearch(arr, 0, arr.length - 1, key);
 if (result != -1)
  System.out.println("Key " + "\"" + key + "\" found at index = " + result);
 else
  System.out.println("Key " + "\"" + key + "\"not found!");
}
}

Explanation

Here, binary search is implemented recursively. If the required key is found in the given array arr, index is returned. Otherwise, if the key is not found, -1 is returned anyway.

As explained in the visualization above, the code follows this procedure:

  • Line 24: Start with the call to recursive binarySearch() function, passing the left and right limits of the array and a key to find.

  • Lines 7-9: Calculate the MidElement index. If the element at the middle index matches the key, return the MidElement index.

  • Lines 11-12: If key is smaller than the element at the MidElement index, make the recursive call passing the left subarray limits (left to mid−1left\ to\ mid-1).

  • Line 14: If key is greater than the element at the MidElement index, make the recursive call passing the right subarray limits (mid+1 to rightmid+1\ to\ right).

  • Line 16: When the element is not found and the array can no longer be subdivided, then return -1 since it is an invalid index.

That’s it! When one of the recursive functions finds the element, it returns that element. Otherwise, -1 is returned anyway.