This lesson introduces the divide and conquer technique of solving a problem using binary search in a sorted array.
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:
- Divide
- Conquer
- 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.
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 indexi
, and the value at indexi-1
is lesser than or equal to the element at indexi
.
How can we use this property? ...