Binary Search

Approach Summary

Classic binary search. Use mid = left + floor((right - left) / 2) to avoid overflow. While left <= right.

Full Solution & Approach

Binary search repeatedly halves the search space. Maintain two bounds lo and hi that bracket the target, with the invariant that if the target exists it lies in [lo, hi]. At each step compute mid = (lo + hi) // 2. If nums[mid] equals target, return mid. If nums[mid] is less than the target, the target must be to the right, so set lo = mid + 1 (mid is already checked). Otherwise set hi = mid - 1. The loop ends when lo > hi, meaning the range is empty and the target is absent — return -1. Each comparison removes roughly half the remaining candidates, so after k steps the search space shrinks from n to about n / 2^k. This only works because the array is sorted — that precondition is what makes the halving valid.

Each iteration halves the range, so the number of iterations is log₂(n) — O(log n) time. Only constant extra space for three integers — O(1).

Solution Code

Solution

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

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

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;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

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

Edge Cases to Watch

Target smaller than every element — lo keeps moving right, ends with -1
Target at index 0
Target at the last index
Empty array or single-element array
Duplicate values — any matching index is acceptable

How to Recognize This Pattern

Sorted array
Find exact target

Complexity Analysis

Time Complexity

O(log n)

Space Complexity

O(1)