Author
Abhinav Rawat
Product Manager @ Interview Kickstart | Ex-upGrad | BITS Pilani. Working with hiring managers from top companies like Meta, Apple, Google, Amazon etc to build structured interview process BootCamps across domains
The binary search algorithm is an efficient and popular searching algorithm. If you are a software developer preparing for a coding interview, you must know this algorithm — it is often used to solve coding interview problems and questions.
Binary search has a wide range of applications — it can also be used to optimize an existing solution. This article will cover everything about the binary search algorithm to help you ace your coding interview.
We’ll cover:
Binary search is a searching algorithm. It is also known as logarithmic search, half-interval search, or binary chop. We often use this algorithm to check if an element is present in a sorted list and to find its position in the list if it is present.
You may have applied this algorithm in real life while playing the guessing game — you ask a friend to think of a number. You take a guess, and your friend tells you if your guess is too low or too high.
You narrow down the expected range and guess again until you get the correct number. Believe it or not, you will be able to guess the number correctly in no more than 20 steps, if the range of the unknown number is up to a million.
Binary search has several other applications.
we can find the root of the equation with great precision if the function f is continuous in the range [x1, x2]
Binary search uses the concept of decrease and conquer:
Let’s go through an example: given a sorted list, let’s try to find out if a query element is present in the list or not. We repeatedly reduce the list to a smaller sublist depending on some conditions. We will compare the query value with the middle element of the list to decide how to reduce the search range— we’ll continue this process until the size of the list reduces to 0 or when we find the query element (i.e., the middle element of the list becomes equal to the query element).
Throughout this article, we are going to explain the above problem and its solution in detail.
Note: In this article, we will consider the middle element of an n sized list as the element at floor ((n – 1) / 2)th index of the list considering 0-based indexing. For example, the middle element of a list of size 5 will be at the index 2 of the list.
The algorithm:Â
Have a look at the following figure to see this in action:
Now that we know how binary search works, let’s put it in pseudocode. You can use this to create your code in any programming language you like.
function recursive_binary_search(A, low, high, target)
  if low > high then
    return -1
  mid := (low + high) / 2
  if target = A[mid] then
    return mid
  else if target > A[mid] then
    return recursive_binary_search(A, mid + 1, high, target)
  else:
    return recursive_binary_search(A, low, mid - 1, target)
â€
function iterative_binary_search(A, n, target)
  low := 0
  high := n - 1
  while low <= 2="" high="" do=""  =""  mid="" :="(low" +="" high)=""  if="" target="A[mid]" then=""  return="" mid=""  else="" if=""> A[mid] then
      low := mid + 1
    else:
      high := mid - 1
  return -1
â€
We’ve demonstrated the binary search code in C, C++, Java, and Python.
#include
int recursive_binary_search(int arr[], int low, int high, int target)
{
  // checking if the size of array has reduced to 0
  if(low > high)
  {
    return -1;
  }
  int mid = (low + high) / 2;
  if(target == arr[mid])
  {
    // found the target
    return mid;
  }
  else if (target > arr[mid])
  {
    // search for the target in the right subarray
    return recursive_binary_search(arr, mid + 1, high, target);
  }
  else
  {
    // search for the target in the left subarray
    return recursive_binary_search(arr, low, mid - 1, target);
  }
}
int main()
{
  int n = 12;
  int arr[] = {3, 7, 12, 15, 22, 23, 30, 41, 74, 83, 92, 95};
  int target = 83;
  int idx = recursive_binary_search(arr, 0, n - 1, target);
  if(idx == -1)
    printf("Target Not Found!!");
  else
    printf("Target found at index = %d", idx);
  return 0;
}
â€
#include
int iterative_binary_search(int arr[], int n, int target)
{
  int low = 0, high = n - 1;
  while(low <= high)=""  =""  {=""  int="" mid="(low" +="" 2;=""  if(target="=" arr[mid])="" found="" the="" target=""  return="" mid;=""  }=""  else="" if="" (target=""> arr[mid])
    {
      // search for the target in the right subarray arr[mid + 1, high]
      low = mid + 1;
    }
    else
    {
      // search for the target in the left subarray arr[low, mid - 1]
      high = mid - 1;
    }
  }
  // target not found
  return -1;
}
int main()
{
  int n = 12;
  int arr[] = {3, 7, 12, 15, 22, 23, 30, 41, 74, 83, 92, 95};
  int target = 83;
  int idx = iterative_binary_search(arr, n, target);
  if(idx == -1)
    printf("Target Not Found!!");
  else
    printf("Target found at index = %d", idx);
  return 0;
}
â€
#include
using namespace std;
int recursive_binary_search(vector arr, int low, int high, int target)
{
  // checking if the size of array has reduced to 0
  if(low > high)
  {
    return -1;
  }
  int mid = (low + high) / 2;
  if(target == arr[mid])
  {
    // found the target
    return mid;
  }
  else if (target > arr[mid])
  {
    // search for the target in the right subarray
    return recursive_binary_search(arr, mid + 1, high, target);
  }
  else
  {
    // search for the target in the left subarray
    return recursive_binary_search(arr, low, mid - 1, target);
  }
}
int main()
{
  vector arr = {3, 7, 12, 15, 22, 23, 30, 41, 74, 83, 92, 95};
  int target = 83;
  int idx = recursive_binary_search(arr, 0, arr.size() - 1, target);
  if(idx == -1)
    cout << "Target Not Found!!";
  else
    cout << "Target found at index = " << idx;
  return 0;
}
â€
#include
using namespace std;
int iterative_binary_search(vector arr, int target)
{
  int n = arr.size();
  int low = 0, high = n - 1;
  while(low <= high)=""  =""  {=""  int="" mid="(low" +="" 2;=""  if(target="=" arr[mid])="" found="" the="" target=""  return="" mid;=""  }=""  else="" if="" (target=""> arr[mid])
    {
      // search for the target in the right subarray arr[mid + 1, high]
      low = mid + 1;
    }
    else
    {
      // search for the target in the left subarray arr[low, mid - 1]
      high = mid - 1;
    }
  }
  // target not found
  return -1;
}
int main()
{
  vector arr= {3, 7, 12, 15, 22, 23, 30, 41, 74, 83, 92, 95};
  int target = 83;
  int idx = iterative_binary_search(arr, target);
  if(idx == -1)
    cout << "Target Not Found!!";
  else
    cout << "Target found at index = " << idx;
  return 0;
}
â€
class RecursiveBinarySearch {
  public static int recursive_binary_search(int arr[], int low, int high, int target)
  {
    // checking if the size of array is 0
    if(low > high)
    {
      return -1;
    }
    int mid = (low + high) / 2;
    if(target == arr[mid])
    {
      // found the target
      return mid;
    }
    else if (target > arr[mid])
    {
      // search for the target in the right subarray
      return recursive_binary_search(arr, mid + 1, high, target);
    }
    else
    {
      // search for the target in the left subarray
      return recursive_binary_search(arr, low, mid - 1, target);
    }
  }
  // Driver method to test above function
  public static void main(String args[])
  {
    int arr[] = {3, 7, 12, 15, 22, 23, 30, 41, 74, 83, 92, 95};
    int target = 83;
    int idx = recursive_binary_search(arr, 0, arr.length - 1, target);
    if(idx == -1)
      System.out.println("Target Not Found!!");
    else
      System.out.println("Target found at index = " + idx);
  }
}
â€
class IterativeBinarySearch {
  public static int iterative_binary_search(int arr[], int target)
  {
    int n = arr.length;
    int low = 0, high = n - 1;
    while(low <= high)=""  =""  {=""  int="" mid="(low" +="" 2;=""  if(target="=" arr[mid])="" found="" the="" target=""  return="" mid;=""  }=""  else="" if="" (target=""> arr[mid])
      {
        // search for the target in the right subarray arr[mid + 1, high]
        low = mid + 1;
      }
      else
      {
        // search for the target in the left subarray arr[low, mid - 1]
        high = mid - 1;
      }
    }
    // target not found
    return -1;
  }
  // Driver method to test above function
  public static void main(String args[])
  {
    int arr[] = {3, 7, 12, 15, 22, 23, 30, 41, 74, 83, 92, 95};
    int target = 83;
    int idx = iterative_binary_search(arr, target);
    if(idx == -1)
      System.out.println("Target Not Found!!");
    else
      System.out.println("Target found at index = " + idx);
  }
}
â€
def recursive_binary_search(arr, low, high, target):
  # checking if the size of array has reduced to 0
  if low > high:
    return -1
  mid = (low + high) // 2
  if target == arr[mid]:
    # found the target
    return mid
  elif target > arr[mid]:
    # search for the target in the right subarray
    return recursive_binary_search(arr, mid + 1, high, target);
 Â
  else:
    # search for the target in the left subarray
    return recursive_binary_search(arr, low, mid - 1, target);
arr = [3, 7, 12, 15, 22, 23, 30, 41, 74, 83, 92, 95]
target = 83
idx = recursive_binary_search(arr, 0, len(arr) - 1, target)
if idx == -1:
  print("Target Not Found!!")
else:
  print("Target found at index = %d" % idx)
â€
def iterative_binary_search(arr, target):
  n = len(arr)
  low = 0
  high = n - 1
  while low <= 2="" high:=""  =""  mid="(low" +="" high)=""  if="" target="=" arr[mid]:=""  #="" found="" the=""  return="" mid=""  elif=""> arr[mid]:
      # search the target in the right subarray arr[mid + 1, high]
      low = mid + 1
   Â
    else:
      # search for the target in the left subarray arr[low, mid - 1]
      high = mid - 1
  # target not found
  return -1
arr = [3, 7, 12, 15, 22, 23, 30, 41, 74, 83, 92, 95]
target = 83
idx = iterative_binary_search(arr, target)
if idx == -1:
  print("Target Not Found!!")
else:
  print("Target found at index = %d" % idx)
â€
Target found at index = 9
The time complexity of binary search is O(log(n)). This is how it can be proven:
The algorithm takes maximum time when the target is found in a 1-sized list, or the target is not found.
We’ll call the size of the list “n†and the number of steps taken to reduce the size of the list to 1 “steps.â€
At each step, the size of the sublist reduces to floor(size of the list * (1 / 2))
Therefore in the worst case, the expression: ceil( n * (½ * ½ * ½  …….. ½) ) = 1will hold.
So, ceil (n * (½) ^ steps) = 1 will also hold.
Therefore, we can conclude that the value of n will be close to 2 ^ steps.
Therefore, steps = log2(n) = O(log(n))
Time required to compare target and the middle element of the list at each step
=Â O(1)
The time complexity of binary search = No of steps * Time required to compare at each step
= O(log(n)) * O(1)
= O(log(n))
In recursive implementation, we make a recursive call at each stage — this means leaving the current invocation on the stack and calling a new one. When we’re k levels deep, we’ve got k lots of stack frames, so the space complexity ends up being proportional to the depth we have to search.
The maximum depth is equal to the number of steps to reduce the size of the list to 1. Hence, the space complexity of the recursive binary search is O(log(n)).
The space complexity of iterative binary search is O(1) because we only used a constant amount of additional space.
Question 1:Recursive or iterative binary search — Which one is more efficient and why?
Answer: Both implementations of binary search have the same time complexity O(log(n)). So, we can’t decide the efficiency based on the time complexity of the algorithm.
The recursive binary search takes O(log(n)) space because of recursion call stack space, whereas iterative binary search only takes constant O(1) space. So, it may look like iterative binary search is more efficient than recursive binary search in terms of memory consumption. But recursive binary search is a tail recursion — which means that the recursion call of the recursive function is the last operation to be executed in a particular branch of control flow in the function. Most modern compilers convert tail recursion into an iterative program. Hence, most of the time, the recursive binary search will not cause any function stack usage issues.
Question 2: Does binary search algorithm work on the principle of divide and conquer?
Answer: No, binary search doesn’t work on the principle of divide and conquer. It works on the principle of “decrease and conquer.â€
Question 3: So, what’s the difference between “divide and conquer†and “decrease and conquer�
Answer: The difference between them is that in divide and conquer, we divide the problem into multiple subproblems and solve each of them individually to form the solution. On the other hand, in decrease and conquer, we decrease, or in other words, reduce the problem to a single and smaller subproblem and solve it to get the solution.
In binary search, we divide the list into two halves, discard one half and search the other half for the target. In other words, we solve only a single shorter subproblem. Hence, binary search is a decrease and conquer algorithm.
If you’re looking for guidance and help with getting started, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
———-
Article contributed by Taara Sinh Aatrey
Time Zone:
Get your enrollment process started by registering for a Pre-enrollment Webinar with one of our Founders.
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
Just drop your name and email so we can send your Power Patterns PDF straight to your inbox. No Spam!
By sharing your contact details, you agree to our privacy policy.
Time Zone: Asia/Dhaka
We’ve sent the Power Patterns PDF to your inbox — it should arrive in the next 30 seconds.
📩 Can’t find it? Check your promotions or spam folder — and mark us as safe so you don’t miss future insights.
We’re hosting a private session where FAANG insiders walk through how they actually use these Power Patterns to crack interviews — and what sets top performers apart.
🎯 If you liked the PDF, you’ll love what we’re sharing next.
Time Zone:
