Binary Search

Problem

Given a sorted array nums and a target value target, return the index of target if it exists. Otherwise return -1.

The input is strictly sorted in ascending order, so every comparison tells you which half can be discarded.

Intuition

Binary search is not "search in a sorted array" so much as "repeatedly destroy half of the remaining search space without losing correctness."

The key invariant is simple:

• if target exists, it is always inside the current interval;
• every comparison with nums[mid] lets us rule out one half immediately.

The cleanest implementation uses a half-open interval [lo, hi). That avoids off-by-one bugs and makes the termination condition obvious: once lo == hi, the interval is empty.

Approach

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut lo = 0usize;
        let mut hi = nums.len();

        while lo < hi {
            let mid= lo + (hi - lo) / 2;
            if nums[mid] < target {
                lo= mid + 1;
            } else if nums[mid] > target {
                hi = mid;
            } else {
                return mid as i32;
            }
        }

        -1
    }
}

function search(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length;

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < target) {
      lo = mid + 1;
    } else if (nums[mid] > target) {
      hi = mid;
    } else {
      return mid;
    }
  }

  return -1;
}

Trace

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

Each step discards exactly half of the remaining interval.

Edge cases

• Empty array — the loop never runs; return -1.
• Single element — either return index 0 or -1 after one comparison.
• Target smaller than all values or larger than all values — the interval shrinks to empty without a match.

Takeaway

Binary search is an invariant game. Write down the interval you are preserving, then make every branch prove that the invariant still holds.

The same template powers #35 Search Insert Position, #74 Search a 2D Matrix, #153 Find Minimum in Rotated Sorted Array, and every "binary search on answer" problem later in the roadmap.