Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

Interview Kickstart has enabled over 3500 engineers to uplevel.

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:**

- What Is Binary Search?
- Binary Search Applications
- How Does Binary Search Work?
- Binary Search Algorithm
- Binary Search Pseudocode
- Binary Search Code
- Binary Search Complexity
- Limitations of Binary Search
- Binary Search FAQs

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.

- Searching for a word in a dictionary
- Debugging a large block of code: Comment out the lower half of the code. If there is still some error — this means that the bug is in the upper half, so remove the lower half and debug the upper half; otherwise, uncomment and debug the lower half recursively in a similar way.
- Finding lower bound and upper bound of an element in a sorted list.
- Retrieving data from a sorted database.
- Finding roots of an equation: Given

- an equation f(x) = 0,
- and two points x1 and x2 such that f(x1) < 0 and f(x2) > 0 holds,

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:

**Decrease:**Reduce the problem to a single smaller subproblem.**Conquer:**Solve the smaller subproblem and obtain its solution. Note that the solution to the subproblem and the solution to the original problem has to be the same (we will derive the subproblem while maintaining this invariant).

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: **

- If the size of the list is 0, we stop the process and conclude that the target element is not present in the array
- Else, we compare the target and the middle element of the list
- If the target is equal to the middle element of the list, we return the position of the middle element as the answer
- Else, if the target is greater than the middle element of the list, we search in the right sublist that starts just after the middle element and discard the left subilst completely.
- Else, the target must be present in the left sublist (or target is not present at all);

so, we search in the left sublist that ends just before mid and discard the right sublist.

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.

We’ve demonstrated the binary search code in C, C++, Java, and Python.

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.

- It isn’t efficient for data structures like linked-list which doesn’t support random access
- Binary searching to find a target value works only when the list is sorted

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

Oops! Something went wrong while submitting the form.