704. Binary Search

Quick Identifier

• Topic: binary-search
• Pattern: Binary Search (Vanilla)
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Bloomberg, Apple
• Frequency: Very High
• LeetCode: 704

Quick Sights

• Time Complexity: O(log n) from the optimal approach.
• Space Complexity: O(1) from the optimal approach.
• Core Mechanism: Given sorted distinct integers nums and target, return the index of target, or -1 if it is missing. Use O(log n) comparisons.

Concept Explanation

Given sorted distinct integers nums and target, return the index of target, or -1 if it is missing. Use O(log n) comparisons.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

• "Sorted array" and "return index" or "find target"
• Explicit O(log n) requirement
• Classic divide-by-half on value vs midpoint

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — O(n) time / O(1) space — scan linearly from left to right.
• Better — same as optimal for this problem; no meaningful intermediate.
• Optimal — O(log n) time / O(1) space — maintain a search window [left, right]; compare target to nums[mid] and halve the window.

Optimal Solution

Go

func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		current := nums[mid]
		if current == target {
			return mid
		}
		if current < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1
}

JavaScript

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

Walkthrough

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

Invariant: if target exists in nums, it always lies in the inclusive range [left, right] until found.

Edge Cases

• Single element: equal to target vs not.
• Target smaller than all / larger than all → -1.
• Length zero (if allowed by constraints).

Pitfalls

• mid := (left+right)/2 overflow in languages with fixed-width ints; use left + (right-left)/2.
• Using left < right with wrong update rule (off-by-one for “found” vs “not found”).
• Forgetting the array is sorted and reverting to linear scan under pressure.

Similar Problems

• 35. Search Insert Position — lower bound / first position ≥ target.
• 74. Search a 2D Matrix — rank mapping for implicit 1D sorted order.
• 33. Search in Rotated Sorted Array — same halving idea with two monotone pieces.

Variants

• Find first or last occurrence of duplicates → adjust equality branch to shrink correct side.
• Search in infinite array → double high bound until nums[high] >= target, then vanilla BS.

Mind-Map Tags

#binary-search #sorted-array #log-n #two-end-window