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: 

1. If the size of the list is 0, we stop the process and conclude that the target element is not present in the array
2. Else, we compare the target and the middle element of the list
3. If the target is equal to the middle element of the list, we return the position of the middle element as the answer
4. 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.
5. 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!

Sign up now!

----------

Article contributed by Taara Sinh Aatrey