Introduction to Divide and Conquer With Binary Search

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., it can’t be further divided. At this point, we start solving these atomic problems and combining (merging) the solutions. So, divide-and-conquer solutions have the following three steps:

1. Divide
2. Conquer
3. Merge

Let’s look at an example to grasp this concept better.

Binary search method

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.

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. 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.

Note: 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:

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

Visualization

The following illustration gives a quick visualization ...