Binary Search Algorithm and Implementations

What is Binary Search?

Binary search is an algorithm used to search for a target element in an ordered or sorted list of values. A sorted list is a list in which all the values present in it are arranged in either ascending or descending order.

Given a sorted list containing some values, binary search algorithm can find out whether any target value is present in the list. The algorithm can also return the position of the target value, if the value is present in the list.

Let’s say we have a sorted/ordered list containing some integers: [1,2,3,4,5]. Using binary search algorithm we can find out if a particular value is in the list. For example, one can test if number 3 is in the list (true) or if number 8 is in the list (false).

If the target value is in the list, we can also obtain the position corresponding to the target element in the list. For example by executing binary search algorithm for number 3 in the list , [1,2,3,4,5], the algorithm returns the position as 3.

But you may ask: Why not just go through all the list elements one by one and check if a target value is present? Let’s find out in the coming sections.

The basic method of searching a list

A naive approach is to iterate through each element in the list one by one until we reach the required element and then conclude that the element exists. If we reach end of the list before finding the required element, we conclude that the element does not exist in the list.

In worst case scenario i.e., if required element is not present in the list, linear search algorithm takes n iterations (size of the list) to just confirm that the required element is not present.

This naive algorithm is known as linear search and it involves visiting all the elements in the list in some scenarios. For example if the required value is the last element in the list or if it is not present in the list, we need to check every value in the list until the last value.

Why use Binary Search?

Binary search algorithm makes very less number of comparisons than the linear search algorithm.

For example, consider a sorted list containing a million (1,000,000) elements and we need to check if some value exists (which is actually present at the end of the list). Using linear search we need to make 1 million comparisons because we check each value from the start of list to the end and finally realize that the last element is what we need!.

But using binary search algorithm we would just need to make around 20 comparisons to find out that the value exists. (1,000,000 comparisons required for linear search vs 20 comparisons for binary search!!)

Note: Even though Binary search algorithm is really fast when compared with linear search algorithm, it can be used only on lists/arrays of values arranged in ascending or descending order (or any content specific ordering).

How does Binary Search work?

Idea behind the algorithm

Let us start simple. Assume that there are 3 values in a list arranged in ascending order. Let the list be [4, 5, 6]. Now we ask someone who doesn’t know the contents of the list to tell us position of a value in the list. For example, if we ask for position of value 5, the answer has to be 2 (value 5 is at 2nd position).

Now let’s ask someone who doesn’t know the contents of the list to tell us position of a value in the list. The person initially sees the list as [*, *, *] (* implies that the value at that position is unknown). All he knows is that the values are in ascending order and that the target value might be somewhere in the list.

We ask him to tell the position of number 6 in the list. If you were to answer, what can be the minimum values that need to be revealed in the list ([*, *, *]) before you can figure out the position of number 6? Think about it.

If you choose linear search algorithm, you would ask to reveal the first element, find out that the value is 4, then reveal the second element, find out that the value is 5 and finally upon revealing the last element 6, you will be able to answer that the target number 6 is at 3rd position.

There is a cleverer way of quickly achieving the same thing. Which is the foundation of binary search algorithm. It uses the fact that if we know that the value of an element at a particular position (say p) is greater than target value, the target value can’t exist to the right of p (Since the list is in ascending order). Similarly if we know that value of element at position p in the list is less than the target value, the required element has to be at a position more than p.

| * | * | * | * | * | y | * | * | * | * | * | * |
|-------------------|   |-----------------------|
|less than valu at p| ^ |greater than value at p|
                 (Position p)

So in previous example, if you ask to reveal the center element, you will see the list as [*, 5, *]. Since the numbers are in ascending order, number 6 cannot be at the first position in list, so we need not reveal the first number. Next you request to reveal the number after 5. The list then becomes [*, 5, 6] and then we conclude that number 6 exists and is present at 3rd position!

For searching large sorted lists, we save a lot of processing power by revealing only potential numbers and ignoring the rest. This algorithm is explained in detail in the next section.

Algorithm Walkthrough

Let’s take an example of a list containing a few numbers arranged in ascending order:

List = [1, 5, 8, 10, 35, 42, 50, 63]

The requirement is to find if any element with a target value exists in the list. And if any element with required value exists, position of the element has to be identified.

Let us mark the positions of all the numbers present in the list for better understanding:

         1   2   3   4    5    6    7    8
List = | 1 | 5 | 8 | 10 | 35 | 42 | 50 | 63 |

Now let’s say we would like to find the position of number 50 in the list. At the beginning, when we have not compared any element, the value of number at each position is unknown to the algorithm. Below is how the algorithm sees the list:

List = | x | x | x | x | x | x | x | x |

Now the algorithm checks for the value at the center position. Below is how the list looks after accessing the center element:

List = | x | x | x | 10 | x | x | x | x |

The revealed element is 10. Because all the values in list are arranged in ascending order, the target element 50 (which is greater than 10), can’t exist before 10. So the algorithm concludes that the number 50 is present somewhere after number 10.

| x | x | x | 10 | x | x | x | x |
|-----------|    |---------------|
less than mid  ^  greater than mid
              mid (50 is somewhere here)

So next algorithm checks the center element in the portion of list which is towards right of number 10.

List = | x | x | x | 10 | x | 42 | x | x |

The number 42 is less than the target number 50. So we need to look towards the right segment again.

List = | x | x | x | 10 | x | 42 | 50 | x |

Finally we see that the number 50 is present at the 7th position in the list. Note that we compared/visited just 3 elements (10, 42, 50) for finding the position. If we used a linear search algorithm, we need to compare all the elements in list from the start to 7th position (the position where the target value is).

TODO: Add AV simulating binary search

Pseudocode of Iterative Binary Search Algorithm

function binary_search(List, Target) is
    LeftBound := 1
    RightBound := size_of(List)
    while LeftBound ≤ RightBound do
        m := floor((LeftBound + RightBound) / 2)
        if List[m] < T then
            LeftBound := m + 1
        else if List[m] > T then
            RightBound := m − 1
        else:
            return m
    return unsuccessful

Explanation: Given a list List of size N, we need to find the position of a target element. Initially we assume the target element to be present anywhere from the 1st to Nth position. With each iteration, we keep reducing the bounds within which we think the required element can be found until we find the target or if the bounds cross each other.

Implementing Binary Search Algorithm

Iterative Binary Search Implementation

# Implementation of Iterative Binary Search in python
def binarySearch(array, target, low, high):

    # Keep reducing bounds until low and high pointers meet each other
    while low <= high:

        # Below is same as (high+low)//2
        # But we do this to prevent overflows
        mid = low + (high - low)//2

        # If we found the target, return it!
        if array[mid] == target:
            return mid

        elif array[mid] < target:
            low = mid + 1

        else:
            high = mid - 1

    return -1


# Let's test the algorithm now
array = [2, 5, 7, 8, 13, 34, 45, 57]
target = 34
result = binarySearch(array, target, 0, len(array)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

// Iterative Binary Search Implementation in C++

#include <iostream>
using namespace std;

int binarySearch(int array[], int target, int low, int high) {
  
  // Repeat until the pointers low and high meet each other
  while (low <= high) {
    
    // The below is same as mid = (high+low)/2
    // But we do the below to prevent overflow
    int mid = low + (high - low) / 2;

    // If we found the target, return it!
    if (array[mid] == target)
      return mid;

    if (array[mid] < target)
      low = mid + 1;

    else
      high = mid - 1;
  }

  return -1;
}

// Let's test the binary search algorithm now
int main(void) {
  int array[] = {2, 5, 7, 8, 13, 34, 45, 57};
  int target = 34;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, target, 0, n - 1);
  if (result != -1)
    cout << "Element is found at index " << result;
  else
    cout << "Element Not found in the list";
}

Recursive Binary Search Implementation

# Implementation of Recursive Binary Search in python

def binarySearch(array, target, low, high):

    if high >= low:

        mid = low + (high - low)//2

        # If we found the target, return it!
        if array[mid] == target:
            return mid

        # Search the left half
        elif array[mid] > target:
            return binarySearch(array, target, low, mid-1)

        # Search the right half
        else:
            return binarySearch(array, target, mid + 1, high)

    else:
        return -1


# Let's test the algorithm now
array = [2, 5, 7, 8, 13, 34, 45, 57]
target = 34
result = binarySearch(array, target, 0, len(array)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

// Implementation of Recursive Binary Search in C++

#include <iostream>
using namespace std;

int binarySearch(int array[], int target, int low, int high) {
  if (high >= low) {
    int mid = low + (high - low) / 2;

    // If we found the target, return it!
    if (array[mid] == target)
      return mid;

    // Search the left half
    if (array[mid] > target)
      return binarySearch(array, target, low, mid - 1);

    // Search the right half
    return binarySearch(array, target, mid + 1, high);
  }

  return -1;
}

// Let's test the binary search algorithm now
int main(void) {
  int array[] = {2, 5, 7, 8, 13, 34, 45, 57};
  int target = 34;
  int n = sizeof(array) / sizeof(array[0]);
  int result = binarySearch(array, target, 0, n - 1);
  if (result != -1)
    cout << "Element is found at index " << result;
  else
    cout << "Element Not found in the list";
}

TODO: Common Errors

Characteristics of Binary Search Algorithm

Time Complexity

Binary search algorithm reduces the search space by half in each iteration. Initially the search space is N (Length of the list), Then the search space is reduced by half to N/2. In the next iteration, the search space becomes N/4. So by the time we make log(N)th iteration, the search space reduces to just a single element. Hence the time complexity of binary search algorithm is O(logN) in worst case scenario.

In the best case scenario, the center element can be the element we are looking for, so just a single iteration is required and hence the best case time complexity is O(1).

Space Complexity

Iterative implementation of binary search algorithm doesn’t consume any extra space apart from the space used to store left and right bounds. So the space complexity of iterative binary search algorithm is O(1).

Recursive implementation of binary search algorithm requires an additional stack space and it’s space complexity is O(logN).

Resources & References

• Khan Academy - Binary Search
• Wikipedia
• Number Guessing Game