Algorithms for Coding Interviews in C++/

...

/

Introduction to Divide and Conquer with Binary Search

Introduction to Divide and Conquer with Binary Search

This lesson introduces the Divide and Conquer technique of solving a problem using Binary Search in a sorted array

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.

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