Binary search

Binary search is a searching algorithm that assumes we have a pre-sorted linear data structure. The premise is simple: we look at the middle element in the structure, and if the element we’re looking at is greater than the middle we look at the top sub-array, and if it’s less, we look at the bottom sub-array.

Say our value is to the left sub-array, then we set our high index as middle - 1. For the opposite case, we set our low index as middle + 1.

Because our search array is divided in half each iteration, we have $n/2^x=1$, i.e., our time complexity is $O(\log n)$.

Implementation

Below is an iterative implementation in C:

int binarySearch(int list[], int length, int key) {
	int low = 0, high = length - 1, index = -1, middle;
	while (low <= high && index == -1) {
		middle = (low + high) / 2;
		if (list[middle] == key) {
			index = middle;
		} else if (list[middle] > key) {
			high = middle - 1;
		} else {
			low = middle + 1;
		}
	}
	return index;
}

We can also implement it recursively, where our base case is that it wasn’t found.

int binarySearchHelper(int list[], int key, int low, int high) {
	if (low > high) { // if not found
		return -1;
	}
	int middle = (low + high)/2;
	if (list[middle] == key) { // if we found it
		return middle;
	}
	if (list[middle] > key) { // if it's on the LHS
		return binarySearchHelper(list, key, low, middle - 1);
	} else if (list[middle] < key) {
		return binarySearchHelper(list, key, middle + 1, high);
	}
}
 
int binarySearch(int list[], int length, int key) {
	return binarySearchHelper(list, key, 0, length - 1);
}