It’s been a while since I’ve been writing on the blog, so I’ve decided to start being more active and since it’s been almost 15 years since I’ve studied this in University, it can also be a good refreshment course for me as well as anyone else looking into refreshing their memory or learning.

Binary search is a very useful algorithm, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.

Binary search is used to find the index of an element in a sorted array, and if the element doesn’t exist, that can be determined efficiently as well. It does it by dividing the input array by half at every step, and after every step, either we have found the index that we are looking for or half of the array can be discarded.

Description

Given a sorted array of integers, return the index of the given key. Return -1 if not found.

Example

Given the following array, if search key is 4, binary search will return 2.

Solutions

There are a couple of ways to solve this problem easily, we can either use a recursive or iterative approach, but before we look into both let’s evaluate the complexity for both solutions, and the algorithms for both solutions.

Algorithm

1. At every step, consider the array between low and high indices
2. Calculate the middle index.
3. If element at the middle index is the key, return middle.
4. If element at middle is greater than the key, then reduce the array size such that high becomes mid - 1. Index at low remains the same.
5. If element at middle is less than the key, then reduce the array size such that low becomes mid + 1. Index at high remains the same.
6. When low is greater than high, key doesn’t exist. Return -1.

Recursive

Runtime complexity

Logarithmic, О(logn)

Memory complexity

Logarithmic, О(logn)

The reason why it has O(logn) memory complexity is because it will have to consume memory on the stack.

Implementation

#include <iostream>
using namespace std;

int binary_search_recursive(int A[], int key, int low, int high) {
  if (low > high) {
    return -1;
  }

  int mid = low + ((high - low) / 2);
  if (A[mid] == key) {
    return mid;
  } else if (key < A[mid]) {
    return binary_search_recursive(A, key, low, mid - 1);
  }

  return binary_search_recursive(A, key, mid + 1, high);
}

int main(int argc, char ** argv) {
  int arr[] = { 1, 3, 4, 6, 7, 8, 10, 13, 14 };
  int size = sizeof(arr) / sizeof(arr[0]);
  cout << "Key(2) found at: " << binary_search_recursive(arr, 2, 0, size - 1) << endl;
  cout << "Key(4) found at: " << binary_search_recursive(arr, 4, 0, size - 1) << endl;
  cout << "Key(9) found at: " << binary_search_recursive(arr, 9, 0, size - 1) << endl;
  cout << "Key(13) found at: " << binary_search_recursive(arr, 13, 0, size - 1) << endl;
  cout << "Key(90) found at: " << binary_search_recursive(arr, 90, 0, size - 1) << endl;
  return 0;
}

After running the application the output is

$ g++ arr-binary-search-rec.cpp
$ ./a.out
Key(2) found at: -1
Key(4) found at: 2
Key(9) found at: -1
Key(13) found at: 7
Key(90) found at: -1

Iterative

Runtime complexity

Logarithmic О(logn)

Memory complexity

Constants, O(1)

Implementation

#include <iostream>
using namespace std;

int binary_search_iterative(int A[], int key, int len) {
  int low = 0;
  int high = len - 1;

  while (low <= high) {
    int mid = low + ((high - low) / 2);
    if (A[mid] == key) {
      return mid;
    } else if (key < A[mid]) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  return -1;
}

int main(int argc, char ** argv) {
  int arr[] = { 1, 3, 4, 6, 7, 8, 10, 13, 14 };
  int size = sizeof(arr) / sizeof(arr[0]);
  cout << "Key(2) found at: " << binary_search_iterative(arr, 2, size - 1) << endl;
  cout << "Key(4) found at: " << binary_search_iterative(arr, 4, size - 1) << endl;
  cout << "Key(9) found at: " << binary_search_iterative(arr, 9, size - 1) << endl;
  cout << "Key(13) found at: " << binary_search_iterative(arr, 13, size - 1) << endl;
  cout << "Key(90) found at: " << binary_search_iterative(arr, 90, size - 1) << endl;
  return 0;
}

After running the application the output is

$ g++ arr-binary-search-iter.cpp
$ ./a.out
Key(2) found at: -1
Key(4) found at: 2
Key(9) found at: -1
Key(13) found at: 7
Key(90) found at: -1

Resources

• Picture for binary search taken from Wikipedia
• If you want to know about different variations of binary search take a look at the wikipedia page