Binary search (array)

O(log n)

Halve the search space each step on sorted data: compare the middle, throw away the half that can't hold the answer.

Signals

sorted arrayfind a target / first or last occurrencen up to 1e6+ and O(log n) expectedfind the boundary where a condition flipssearch a rotated-but-mostly-sorted array (with a twist)

Template

function binarySearch(arr, target) {
    let lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Looks similar, isn't

Linear search: Use binary only when the data is actually sorted and n is large enough that O(log n) matters. On unsorted data or tiny n, sorting first costs more than a linear scan saves.
Binary search on a rotated array: Plain binary search assumes the whole array is sorted left to right. A rotated array breaks that assumption; you must first work out which half is still sorted before you can discard one.

sorted array, n up to 1e6+, need faster than O(n) -> O(log n) time, O(1) space. Sorted + large n is the cue; without sorted order binary search cannot run.

Learn this pattern