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
What Is Binary Search?
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.
Binary Search 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]
How Does Binary Search Work?
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.
Binary Search Algorithm (Finding Target in a Sorted 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:
Binary Search Pseudocode
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.
Recursive Implementation
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)
Iterative Implementation
function iterative_binary_search(A, n, target)
low := 0
high := n - 1
while low <= high do
mid := (low + high) / 2
if target = A[mid] then
return mid
else if target > A[mid] then
low := mid + 1
else:
high := mid - 1
return -1
Binary Search Code
We’ve demonstrated the binary search code in C, C++, Java, and Python.
Binary Search Code in C
Recursive Implementation
#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;
}
Iterative Implementation
#include
int iterative_binary_search(int arr[], int n, int target)
{
int low = 0, high = n - 1;
while(low <= high)
{
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 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;
}
Binary Search Code in C++
Recursive Implementation
#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;
}
Iterative Implementation
#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 + high) / 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;
}
Binary Search Code in Java
Recursive Implementation
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);
}
}
Iterative Implementation
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 + high) / 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);
}
}
Binary Search Code in Python
Recursive Implementation
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)
Iterative Implementation
def iterative_binary_search(arr, target):
n = len(arr)
low = 0
high = n - 1
while low <= high:
mid = (low + high) // 2
if target == arr[mid]:
# found the target
return mid
elif target > 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)
Code Output
Target found at index = 9
Binary Search Complexity
Time Complexity
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))
Space Complexity
Recursive Implementation
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)).
Iterative Implementation
The space complexity of iterative binary search is O(1) because we only used a constant amount of additional space.
Limitations of Binary Search
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
Binary Search FAQs
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.
Are You Ready to Nail Your Next Coding Interview?
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!
.png)
