How to implement Binary search in an easy way

Introduction

Binary Search is a simple and efficient search algorithm that works on a given set of elements to find the occurrence of a target search interest. The prerequisite of this search algorithm is that the target set of elements on which it operates should be a sorted set (in some order).

The algorithm improves over the traditional linear search approach where you just loop through all the elements in the set and do a one-on-one comparison on the current element on the set with the target element, such that while a traditional linear search takes O(N) time to perform the search operation in its worst-case, the Binary Search does it in O(logN) time.

Let’s start by understanding how a linear search works and then see how Binary Search scores against this:

Simple Search – How to implement Linear search with an Example

For a given set A containing N elements, we need to find the index at which the target element E occurs in the set. The linear search does it as below:

function LinearSearch(array A, integer N, integer E)
begin
    currentIndex = 0
    while currentIndex < N do
    begin
        if A[currentIndex] == E then
        begin
            return currentIndex // a match found
        end
        else
        begin 
            currentIndex = currentIndex + 1
        end
    end
    return -1 // no matching element was found 
end

In this algorithm, the time taken for the lookup grows linearly as the input set A grows in size. Hence the worst case complexity of this search is O(N) where N is the number of elements in the set.

How to implement Binary Search algorithm

In case of a Binary Search, we know that the set is already sorted. Hence, for any given iteration, we examine only “half” of the given input set for the target element and if it is not found, we’ll further reduce the lookup to smaller subsets, until we run out of the elements. The mechanism is like below:

1. Define leftIndex and rightIndex for the input set on which the lookup happens.
2. Determine the midpoint of this set midIndex = Average(left, right)
3. Check if the targetElement is present at this midIndex or not. If present, the search ends with the midIndex as the required output
4. if the midIndex doesn’t contain the targetElement, check if the element at midIndex is less than or greater than the targetElement
5. if the targetElement is less than the element at midIndex, it means the element might exist to the “left” of the midIndex, otherwise “right”.
6. At this point, the algorithm reduces the set to lookup for the targetElement either to the “left” subset or “right” subset of the midIndex.
7. The algorithm further continues till the leftIndex and the rightIndex overlap with each other, which means the element doesn’t exist.

We can implement this in a regular loop:

function BinarySearch(array A, integer leftIndex, integer rightIndex, integer target)
begin
    while leftIndex > rightIndex do
    begin
        midIndex = (leftIndex + rightIndex) / 2
        if A[midIndex] == target then
        begin
            return midIndex // element found
        end
        else if A[midIndex] > target then // element falls on the left subset
        begin
            right = midIndex - 1
        end
        else 
        begin 
            left = midIndex
        end
    end
    return -1 // element not found
end

Or in a recursive fashion:

function BS_Recursive(array A, integer leftIndex, integer rightIndex, integer target)
begin
    if leftIndex > rightIndex then 
    begin
        return -1
    end

    midIndex = (leftIndex + rightIndex) / 2
    
    if A[midIndex] == target then
    begin
        return midIndex // element found
    end
    
    if A[midIndex] > target then // element falls on the left subset
    begin
        return BS_Recursive(A, left, mid - 1, target)
    end
    else 
    begin 
        return BS_Recursive(A, mid, right, target)
    end
end

Binary Search algorithm example in .NET

public int DoBinarySearch(int[] array, int left, int right, int searchElement)
{
    if (left > right) return -1;
    int mid = (left + right) / 2;
    
    if (array[mid] == searchElement) return mid;
    
    if (array[mid] > searchElement) 
        return DoBinarySearch(array, left, mid - 1, searchElement);
    else 
        return DoBinarySearch(array, mid, right, searchElement);
}

#Invoking#
DoBinarySearch(array, 0, array.Length - 1, searchElement);

public int DoBS_NoRecursion(int[] array, int left, int right, int searchElement)
{
    while (left < right)
    {
        var mid = (left + right) / 2;
        if (array[mid] == searchElement) return mid;

        if (array[mid] > searchElement)
        {
            right = mid - 1;
        }
        else
        {
            left = mid;
        }
    }

    return -1;
}

#Invoking#
DoBS_NoRecursion(array, 0, array.Length - 1, searchElement);

Binary Search Time Complexity analysis

As we can see, for every iteration (or recursion), the algorithm works on exactly “half” of the initial subset that the algorithm works at the beginning. And hence we have the time taken can be written as:

T(n) = T(n/2) + c // where c is a constant time taken for the comparison

When we expand on this relation for every branch of the call tree, the total work done is equal to the depth of the tree which is O(logN). Hence the total time taken for this search operation always lies within O(logN).

Conclusion

Although BinarySearch is an efficient search algorithm, the prerequisite that it can work only on a sorted set of elements makes it less efficient over larger datasets. When a sorted set of elements are involved for lookup, datastructures such as HashTables can manage to keep the lookup time for as less as O(1) when compared to O(logN) in this case.

But the implementation of the Binary Search finds several usecases such as finding the possible position for an insertion, and so on. And this algorithm also gives way to some of the other divide and conquer algorithms such as QuickSort and MergeSort which work in a similar fashion and take O(NlogN) time for sorting.