Binary search

On a sorted array, look at the middle and throw away the half that cannot contain the target.

Time O(log n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Keep a window [lo, hi] that must contain the target if it exists. Each comparison with the middle element halves the window, so 1,000,000 items need about 20 steps.

Code

C++PythonC#

int binarySearch(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

def binary_search(a: list[int], target: int) -> int:
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target: return mid
        if a[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

public static int BinarySearch(int[] a, int target) {
    int lo = 0, hi = a.Length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Tips

The loop condition is lo <= hi. Using < skips the last remaining element.
The same pattern solves "first value ≥ x", search on the answer, and rotated-array problems.

In the .NET library

Array.BinarySearch and List<T>.BinarySearch. When the value is missing they return a negative number: ~result is the index where it would be inserted.