Binary search (array)

How does Binary search (array) work?

Keep two bounds, low and high, over the sorted range. The answer, if any, lies between them.

Take the middle index of that range. Compare the value there against the target.

On a match the search is over. Return that index.

If the middle value is too small, the target lies to the right. Move low past the middle.

If it is too large, move high below the middle. Half the range disappears either way.

The loop ends when low passes high. The range is empty, so the target is absent.

Sources: Wikipedia: Binary search, Python docs: bisect

1. lo=0 hi=5Looking for 7 in [1, 3, 5, 7, 9, 11]. Six candidates.
2. mid=2, value 55 is smaller than 7. Everything left of it is out.
3. lo=3 hi=5, mid=4, value 99 is larger than 7. Everything right of it is out.
4. lo=3 hi=3, mid=3, value 7One candidate is left, and it matches.
5. return 3Three comparisons for six elements. Doubling the input adds one.

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;
}

function binarySearch(arr: number[], target: number): number {
    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;
}

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

function binarySearch(array $arr, $target) {
    $lo = 0; $hi = count($arr) - 1;
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($arr[$mid] === $target) return $mid;
        if ($arr[$mid] < $target) $lo = $mid + 1;
        else $hi = $mid - 1;
    }
    return -1;
}

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

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

A worked example of Binary search (array)

First and last position of a value

A sorted array can hold the same value many times over. Return the first and last index of a target.

If the value is missing, return minus one twice.

Run the search twice with a different tie-break.

For the first index, keep pushing high left after a match. For the last, keep pushing low right.

function searchRange(nums, target) {
    function bound(findFirst) {
        let lo = 0;
        let hi = nums.length - 1;
        let found = -1;

        while (lo <= hi) {
            const mid = lo + Math.floor((hi - lo) / 2); // cannot overflow

            if (nums[mid] === target) {
                found = mid;
                // a match is not the end: keep squeezing the chosen side
                if (findFirst) hi = mid - 1;
                else lo = mid + 1;
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return found;
    }

    return [bound(true), bound(false)];
}

When should you use Binary search (array)?

Use Binary search (array) when the problem statement says “sorted array”, “find a target / first or last occurrence” or “n up to 1e6+ and O(log n) expected”. A solution built on it usually runs in O(log n).

• •sorted array
• •find a target / first or last occurrence
• •n up to 1e6+ and O(log n) expected
• •find the boundary where a condition flips
• •search a rotated-but-mostly-sorted array (with a twist)

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Binary search (array) confused with?

Binary search (array) is most often confused with Linear search, Binary search on a rotated array, Binary search on the answer, Binary search tree and Two pointers (opposite ends).

• Linear search: A scan reads every element but assumes no order. Binary search demands order and reads log n.
• Binary search on a rotated array: A rotation breaks the single sorted run. The check must find the sorted half first.
• Binary search on the answer: There the range is the set of possible answers, not an array. The test is a function you write.
• Binary search tree: A tree halves the same way but through pointers. It also allows inserts, which an array does not.
• Two pointers (opposite ends): Both ends move there, and the pair being tested changes. Here only one bound moves per step.

Common mistakes with Binary search (array)

• Computing mid as lo plus hi over two

  That sum can pass the safe integer range. Write lo plus half of the gap.

• Moving a bound to mid instead of past it

  The range stops shrinking and the loop never ends. Use mid plus one or mid minus one.

• Mixing the two loop shapes

  With lo <= hi both ends are inclusive. Changing one end alone breaks the invariant.

• Searching data that is not sorted

  The comparison assumes everything left of mid is smaller. Without that the answer is silently wrong.

Which interview problems use Binary search (array)?

Interview problems solved with Binary search (array) include Binary search, Search insert position, First and last position of an element, Find peak element, Sqrt of x, Search a 2D matrix and Smallest letter greater than target.

• Binary search: The plain form over distinct sorted values.
• Search insert position: Return where the value would belong if it is missing.
• First and last position of an element: Two searches with opposite tie-breaks.
• Find peak element: Compare against the neighbour instead of a target.
• Sqrt of x: The sorted range is the set of answers, not an array.
• Search a 2D matrix: Treat the whole grid as one sorted list.
• Smallest letter greater than target: An upper bound that wraps back to the start.

What is the time and space complexity of Binary search (array)?

The target complexity of Binary search (array) is O(log n).

n up to 1e9 is fine, because log2 of 1e9 is about 30. Time is O(log n), space is O(1).