058 — Binary Search

58 — Binary Search

LeetCode 704 · Easy. Given an array of integers nums sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, return its index; otherwise return -1. The algorithm must run in O(log n) time.

---

🍽️ Intuition

This is the pattern's namesake problem — no rotation, no answer-space trick, just a plain sorted array and a target to find. Picture flipping through a dictionary: you don't start at page 1 and read every word. You open to the middle, see which half the word you're after falls in, and throw away the other half. Repeat on what's left. Every comparison halves the remaining pages until you land on the word (or run out of pages, meaning it isn't there).

---

🚩 Pattern-Recognition Cue

"Sorted array" plus "O(log n)" in the same sentence is about as direct a signal as this pattern ever gives. There's no rotation, no duplicated structure, no answer-space feasibility check to design — just a monotonic sequence and a target, which is exactly the textbook shape Binary Search was built for.

---

🐢 Brute Force

Scan every element until the target turns up.

func searchBruteForce(_ nums: [Int], _ target: Int) -> Int {
    for (index, value) in nums.enumerated() {
        if value == target {
            return index
        }
    }
    return -1
}

// smoke test
print(searchBruteForce([-1, 0, 3, 5, 9, 12], 9))   // 4
print(searchBruteForce([-1, 0, 3, 5, 9, 12], 2))   // -1

Big-O: O(n) time — worst case (target absent, or at the very end) touches every element. O(1) space.

---

🚀 Optimal

Maintain a shrinking [lo, hi] window and compare against the midpoint each step.

func search(_ nums: [Int], _ target: Int) -> Int {
    var lo = 0
    var hi = nums.count - 1

    while lo <= hi {
        let mid = lo + (hi - lo) / 2   // avoids Int overflow vs. (lo + hi) / 2

        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }

    return -1
}

// smoke test
print(search([-1, 0, 3, 5, 9, 12], 9))   // 4
print(search([-1, 0, 3, 5, 9, 12], 2))   // -1
print(search([], 5))                       // -1
print(search([5], 5))                      // 0

Big-O: O(log n) time — the window halves every iteration. O(1) space.

---

🔑 The Key Insight

Sortedness is what makes discarding half the array safe. A linear scan can't skip anything because it has no guarantee about what's beyond the element it's currently looking at. But once you know nums[mid], sortedness tells you everything about which side the target could possibly be on: if nums[mid] < target, every index to the left of mid is even smaller than nums[mid] and therefore also too small — the entire left half is provably useless and can be thrown away without checking a single one of its elements. That's the whole trick: sortedness turns "compare one element" into "eliminate half the array," which is what compresses O(n) down to O(log n).

---

🔗 Related Chapters

• Binary Search — this problem is the pattern chapter's canonical example: a sorted array, a target, and a shrinking [lo, hi] window.
• Arrays & Strings — the underlying data structure, and the source of the O(1) random-access-by-index that makes checking nums[mid] free.
• Big-O Notation — for the O(n) → O(log n) reasoning above.

---

🧸 Memory Sentence

Binary Search is flipping straight to the middle of a dictionary instead of reading page by page — every glance at the midpoint throws away half of what's left.

---

✅ Check Your Understanding

Trace the optimal algorithm on nums = [1, 3, 5, 7, 9, 11], target = 7. What are lo, hi, and mid at each iteration, and how many comparisons does it take to find the answer versus how many the brute force would need?

---

⬅️ Previous: Largest Rectangle in Histogram · Next: Search a 2D Matrix ➡️