Introduction to Divide and Conquer with Binary Search

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.

Now we could go about searching the array in a linear manner, ...