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., 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 take an example to grasp this concept better.

Binary search method

Consider a sorted list lst, of n integers. We are required to find if a particular integer value exists in the given list or not.

Now, we could go about searching the list in a linear manner, starting from the 0th index, checking the value at each index as we move towards the 10th index. But a fascinating property of sorted lists 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 lists, 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. lst[i] == k, in which case we have found the key
2. lst[i] < k, in which case the key must exist in the right sublist (considering the