Binary Search

What is binary search?

Suppose you look for a word in a dictionary. You do not read every page from the start — you open near the middle, see if your word is before or after, and jump. Binary search does exactly this on a sorted array, and it is dramatically faster than checking each element one by one.

The one rule: the array must be sorted first. That is what lets binary search safely throw away half the data each step.

The halving idea

Keep three markers: low, high, and the mid between them. Compare the target with the middle:

• If it equals mid — found it.
• If it is smaller — the answer must be in the left half, so move high down.
• If it is larger — it must be in the right half, so move low up.

Each comparison removes half of what is left. That is the whole trick.

Iterative program

#include <stdio.h>
int binarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key)      return mid;   // found
        else if (a[mid] < key)  low = mid + 1; // go right
        else                    high = mid - 1; // go left
    }
    return -1;                  // not found
}
int main() {
    int a[] = {10, 20, 30, 40, 50};
    int pos = binarySearch(a, 5, 40);
    if (pos != -1) printf("Found at index %d\n", pos);
    else           printf("Not found\n");
    return 0;
}

Dry run

Searching for 40 in {10, 20, 30, 40, 50}:

Just two comparisons instead of four — and the gap grows huge as the array gets bigger.

Recursive program

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

Same logic, expressed by calling itself on the chosen half instead of looping.

Why it is so fast

Because each step halves the data, binary search runs in O(log n) — a million items need only about twenty checks.

Common mistakes

• Running it on an unsorted array — the result is meaningless.
• Using (low + high) / 2, which can overflow; prefer low + (high - low) / 2.
• Wrong loop condition — it must be low <= high, not <.
• Forgetting to move past mid with mid + 1 / mid - 1, causing an infinite loop.

Summary

• Binary search finds a value in a sorted array by halving each step.
• Compare with the middle; keep the half that could contain the target.
• Use low + (high - low) / 2 for the middle to avoid overflow.
• Iterative and recursive versions give the same result.
• It runs in O(log n) — far faster than linear search on large data.