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 , i.e., our time complexity is .
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);
}