287. Binary Search

Because the array is sorted, one comparison against the middle element eliminates half of the remaining candidates each step.

Walk-through

1. Keep a closed search range [lo, hi], starting at lo = 0, hi = len(nums) - 1.
2. While lo <= hi:
   • Compute mid = lo + (hi - lo) // 2 (avoids overflow in languages with fixed-width ints).
   • If nums[mid] == target, return mid.
   • If nums[mid] < target, the answer must be to the right → lo = mid + 1.
   • Else the answer is to the left → hi = mid - 1.
3. If the range empties without a match, return -1.

Worked example

nums = [-1, 0, 3, 5, 9, 12], target = 9:

• lo=0, hi=5, mid=2, nums[2]=3 < 9 → lo=3.
• lo=3, hi=5, mid=4, nums[4]=9 == 9 → return 4.

Each step halves the window: 6 → 3 → 1 candidates, so at most ⌈log₂ 6⌉ = 3 probes.

Complexity

• Time: O(log n) — the window size halves every iteration.
• Space: O(1) — only a few index variables.

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, 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;
    }
}