Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C++

Introduction to Divide and Conquer with Binary Search

Explore how to apply the divide and conquer algorithmic paradigm through binary search. Learn to break down a sorted array into subproblems, solve each recursively, and combine solutions. This lesson helps you grasp the process and time complexity of binary search as an efficient search technique.

We'll cover the following...

Divide and Conquer Method

Divide and conquer is an algorithmic paradigm in which the problem is repeatedly divided into sub-problems 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. So, Divide and Conquer 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. 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 0th index, checking the value at each index as we move towards the 10th index. But a fascinating property of sorted arrays is that regardless of the element we are looking at, we can be sure that the next element will either have a value greater than or equal to the current element. Similarly, the previous element will either have a value lesser than or equal to the current element.

In sorted arrays, the value at index i+1 is greater than or equal, 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 at any particular index i, there are three possibilities:

  1. arr[i] == k, in which case we have found the key
  2. arr[i] < k, in which case the key must exist in the right sub-array (considering the array is sorted in ascending order)
  3. arr[i] > k, in which case the key must exist in the left sub-array (considering the array is sorted in ascending order)

Time Complexity

If we start from the middle, we will be able to use this technique to drop half of the array entries at each step and only look at half the keys afterwards; this is logarithmic behavior. Hence, the time complexity of this solution of finding an element in a sorted array is O(log n)O(log \ n).

Visualization

Code

C++
#include <iostream> 
using namespace std; 
// Below is a binary search function implemented recursively
// If the required element, x, is in the given array, arr, its location will be returned
// Otherwise, if the element is not in the array, -1 will be returned
int BinarySearch(int arr[], int left, int right, int x) { 
	if (right >= left) { 
		int MidElement = left + (right - left) / 2; 
		// If the required element is found at the middle index
		if (arr[MidElement] == x) 
			return MidElement; 
		// If the required element is smaller than the element at the middle index 
    // It can only be present in the left subarray 
		if (arr[MidElement] > x) 
			return BinarySearch(arr, left, MidElement - 1, x); 
		// Otherwise, it would be present in the right subarray  
		return BinarySearch(arr, MidElement + 1, right, x); 
	} 
	//If the element is not in the array
	return -1; 
} 
int main(void) { 
	int arr[] = { 2, 4, 7, 25, 60 }; 
	int x = 25; // to find, feel free to change this
	int n = sizeof(arr) / sizeof(arr[0]); 
	int result = BinarySearch(arr, 0, n - 1, x); 
	(result == -1) ? cout << "Element is not present in the array"
				: cout << "Element is present at the index " << result; 
	return 0; 
}

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

  • (Line 32): Start with the call to recursive binarySearch() function, passing the left and right limits of the array and element to find x.
  • (Line 9, 12-13): Calculate the MidElement index. If the element at the middle index matches the x, return MidElement index.
  • (Line 17-18): If x is smaller than the element at the MidElement index, make the recursive call passing only the left subarray limits.
  • (Line 21): If x is greater than the element at the MidElement index, make the recursive call passing only the right subarray limits.

And that’s it. When one of the recursive functions finds the element, it will return that element. Otherwise, −1-1 is returned from the last recursive call (Line 25).