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.
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.
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
The time complexity of binary search = No of steps * Time required to compare at each step
= O(log(n)) * O(1)
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