A catalog lookup keeps SKU codes in a sorted array. On every storefront request the first version walked from index 0 looking for the SKU. A few hundred codes returned instantly. After the marketplace ingest, two million codes were still scanning when the request timed out.

Binary Search asks for the index of a target in a sorted array. An array already gives a[i] for free. A scan uses that and still pays O(n). The sort is the license to discard, not decoration.

This is an interview writeup, not a procedure lecture. The binary search post owns the invariant, lower/upper bound, and Arrays.binarySearch’s miss encoding. Here we only care about membership: inclusive lo / hi, a mid that does not overflow, and -1 when the window is empty.

The problem

Given a non-decreasing int[] nums and an int target, return an index i such that nums[i] == target. If no such index exists, return -1. Typical interviews want O(log n) time.

nums = [4, 9, 11, 18, 27], target = 18  →  3
nums = [4, 9, 11, 18, 27], target = 12  →  -1
nums = [5],                target = 5   →  0

Note: If the array is not sorted, discarding a half is a lie. You can still pick a mid and return a number; that number is not a search result. Confirm the ordered invariant before you write the loop.

Linear scan is the honest brute force

Every index is compared once. Correct. Linear.

int searchLinear(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            return i;
        }
    }
    return -1;
}

At n = 20 this is a rounding error. At n in the millions you paid a full walk for a question a sorted range answers in a handful of probes: is the target still in this half?

Inclusive lo/hi: discard the half that cannot hold it

Keep inclusive bounds: lo and hi are valid indices, and if the answer exists it still sits in nums[lo] .. nums[hi]. Mid is lo + (hi - lo) / 2 so a large int index cannot overflow into a negative mid.

  • If nums[mid] == target, return mid.
  • If nums[mid] < target, everything at or left of mid is too small: lo = mid + 1.
  • If nums[mid] > target, everything at or right of mid is too large: hi = mid - 1.

lo > hi means the invariant has nothing left. Return -1.

nums = [4, 9, 11, 18, 27]   target = 18
        0  1   2   3   4

lo=0 hi=4 mid=2  nums[2]=11  11<18  → lo=3
lo=3 hi=4 mid=3  nums[3]=18  hit, return 3

miss 12:
lo=0 hi=4 mid=2  nums[2]=11  11<12  → lo=3
lo=3 hi=4 mid=3  nums[3]=18  18>12  → hi=2
lo=3 hi=2  empty — return -1

The Java is that loop:

int search(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

Time is O(log n) — each comparison throws away half the remaining range. Space is O(1) — two indices, no extra table. Off-by-one and the JDK miss encoding already live on the algorithms post; do not re-lecture them unless they ask.

Note: Write mid = lo + (hi - lo) / 2, not (lo + hi) / 2. Inclusive while (lo <= hi) must drop mid on every miss (lo = mid + 1 or hi = mid - 1). Setting hi = mid on this contract never terminates when lo == hi.

What interviewers usually poke next

  • First or last occurrence. Duplicates make “an index” the wrong stop. Lower/upper bound are a different problem with a different halt; name that, do not pretend this loop returns the leftmost.
  • Rotated sorted array. Search in a rotated array is a different problem. The range is no longer one sorted slice; you first decide which half is still ordered.
  • Duplicates here. Any equal index is legal. Do not keep shrinking after a hit unless they asked for a bound.
  • Empty / null. hi becomes -1, the loop never runs, return -1. In production you would reject null; at the board, ask.

You are done with this problem when you can say, out loud, why the linear scan is correct, why the sorted invariant licenses discarding a half, and why mid is lo + (hi - lo) / 2.