Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Introduction to Divide and Conquer with Binary Search

Explore how to apply the divide and conquer algorithmic paradigm through binary search. Learn to break down a sorted array into subproblems, solve each recursively, and combine solutions. This lesson helps you grasp the process and time complexity of binary search as an efficient search technique.

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