Binary search with algorithm and example

Binary search finds a key in a sorted array by repeatedly comparing it with the middle element and discarding the half that cannot contain it.

Algorithm

BINARYSEARCH(a, n, key)
1. low = 0, high = n - 1
2. while low <= high
3.     mid = (low + high) / 2
4.     if key == a[mid]  return mid        // found
5.     else if key < a[mid]  high = mid - 1  // search left half
6.     else  low = mid + 1                 // search right half
7. return -1                               // not found

int binarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] == key) return mid;
        else if (key < a[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

Example: search 23 in 5, 12, 18, 23, 30, 41, 56 (index 0 to 6)

Search 41 in the same list:

If the key is absent (say 20), low becomes greater than high and the search stops with "not found".

Complexity: each step halves the range, so the worst case is O(log₂ n) comparisons (best case O(1)). The list must already be sorted and stored in an array that allows direct access.