Binary Search (LC 704)
nums is an integer array sorted in ascending order, and target is an integer; find where target sits in nums. Return that index if target is present, or -1 if it isn't.
Your algorithm must run in O(log n) time.
Worked Examples
nums = [-1,0,3,5,9,12], target = 94nums = [-1,0,3,5,9,12], target = 2-1⚖️Formal Constraints & Bounds
1 <= nums.length <= 104-104 < nums[i], target < 104All the integers in
numsare unique.numsis sorted in ascending order.
Core Insight
If target is in the sorted list, it is at the first index whose value is at least target. Lower Bound finds that index. One look at it answers the question.
Real-World Scenario & Production Applications
When looking up a record in an indexed B-Tree in PostgreSQL or searching an in-memory sorted cache, you never scan sequentially from the beginning. You jump to the middle, determine whether your key comes alphabetically or numerically before or after, and discard half the data space in a single CPU cycle.
Subproblems & Recurrence Decomposition3 Phases
Ask each index one yes-or-no question: nums[i] >= target. The answers are False before target's position and True from it on. Use the range [lo, hi) = [0, len(nums)), so len(nums) stays a possible answer.
# Check: False before target's position, True from it on
def at_least_target(i):
return nums[i] >= target
lo, hi = 0, len(nums)Step-by-Step Execution Trace Table
| Step | Range [lo, hi) | mid | nums[mid] | Check nums[mid] >= 9 | Decision | New range [lo, hi) |
|---|---|---|---|---|---|---|
| 1 | [0, 6) | 3 | 5 | False | 5 is smaller than 9, so the first True is after mid: lo = mid + 1 | [4, 6) |
| 2 | [4, 6) | 5 | 12 | True | mid may be the first True, so keep it: hi = mid | [4, 5) |
| 3 | [4, 5) | 4 | 9 | True | mid may be the first True, so keep it: hi = mid | [4, 4) |
| 4 | [4, 4) | The range is empty. Lower Bound returns i = 4. | ||||
| Look | nums[4] is 9 | 4 < len(nums) and nums[4] == 9 | Return index 4 |
| 1 | def at_least_target(i): |
| 2 | return nums[i] >= target |
| 3 | lo = 0 |
| 4 | hi = len(nums) |
| 5 | i = binary_search_lower_bound(lo, hi, at_least_target) |
| 6 | if i < len(nums) and nums[i] == target: |
| 7 | return i |
| 8 | return -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Exact Match asks whether a key is in a sorted list, and at which index. The answer is one look after a Lower Bound search. If the key is in the list, it sits at the first index whose value is at least the key. So find that index, and look at it.
🏟️ The Analogy: Opening an Alphabetized Physical Dictionary
Imagine looking up the word "Quasar" in a physical 2,000-page dictionary. You don't start at page 1 and read every word. You open the book roughly in the middle, landing on the letter "M". Since "Q" comes after "M", you instantly disregard pages 1 through 1,000 with your left hand. You then split the remaining pages 1,001 through 2,000 in half, landing on "T". Since "Q" comes before "T", you disregard pages 1,500 through 2,000. Each physical split discards hundreds of pages in constant time.
🔑 Why It Works
Every index before the first True holds a value smaller than the key, and the first True holds a value that is at least the key. If that value is equal to the key, it is the first copy. If it is larger, the key is not in the list. When every value is smaller, Lower Bound returns len(nums), and there is nothing to read, so the check i < len(nums) comes first.`,
Reading
nums[i]without checkingi < len(nums): Lower Bound returnslen(nums)when every value is smaller thantarget. There is no value at that index, sonums[i]raises anIndexError.Using
nums[i] == targetas the check: Lower Bound needs a row that reads False…False True…True. The row ofnums[i] == targetis True at one index only.Expecting any copy of
target: the template returns the first copy. The older closed-range loop returns the copy that it reaches first.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
You are given a sorted list and need the index of one value, or a sign that it is missing. The problem asks for better than O(N) time, so each step must remove half of the candidates.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: if target is in nums, it is at the first index whose value is at least target. The check nums[i] >= target is False for every index before that position and True from it on, so Lower Bound can find it. One look at that index then tells whether target is there.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Exact Match. The array is sorted, so the check nums[i] >= target is False before target's position and True from it on. I run Lower Bound over [0, len(nums)) with that check, and it returns the first index whose value is at least target. Then I look at that one index. If i < len(nums) and nums[i] == target, I return i. Otherwise I return -1. The trap is reading nums[i] when i equals len(nums), so I check the bound first. Lower Bound halves the range on every pass, so the time is
O(log n), and the space isO(1)."
Complexity & Mathematical Proof
O(log N)
Look at the loop in Lower Bound: while lo < hi:. Each pass computes mid and evaluates nums[mid] >= target in O(1). Then it keeps [lo, mid) or [mid + 1, hi), so the range loses at least half of its candidates. At most floor(log2 N) + 1 passes run (see the stages below). The final look at nums[i] is one comparison, so the total is O(log N) time.
O(1)
Look at the memory used: the loop is iterative, so the call stack holds one frame. Inside the function we store only the integers lo, hi, mid and i. We allocate no extra arrays, hash tables, or objects. Auxiliary space is O(1).
Derivation Progression
Window Size: N ⟹ N/2 ⟹ N/4 ⟹ ... ⟹ 1
The loop begins with a range of N candidates. Testing nums[mid] >= target removes half of the remaining candidates on every pass.
O(1) arithmetic + comparison
Calculating mid = lo + (hi - lo) // 2 and reading nums[mid] takes O(1) time, with no inner loop.
Total Steps = floor(log2 N) + 1 ⟹ O(log N)
Dividing N by 2 repeatedly reaches window width <= 1 in at most floor(log2 N) + 1 iterations.
Variable Definitions
Total number of elements in the sorted array
Memory Architecture & Bounds
O(1) Iterative while loop with zero recursion frames
O(1) Only scalar pointers (lo, hi, mid) in CPU registers
O(1) Returns a single integer index
Boundary Best / Worst Cases
— Lower Bound does not stop when it meets target, so even the best case runs every halving pass.
— Search requires approximately comparisons.
— Target is at the boundary leaf index or absent from the array.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
When I scan this problem statement, the immediate dead giveaways are the phrases "sorted in ascending order" and the explicit constraint the solution has to run in O(log n) time. A sorted array with unique elements where we are asked to find the index of a single target value is the canonical trigger for Exact Match. It tells me this is not a boundary or answer-space problem on its own. It is Lower Bound plus one look: the check nums[i] >= target is False before target's position and True from it on, so Lower Bound finds where target would go, and one look at that index tells me whether it is there.
The array length means an linear scan would technically execute in a fraction of a millisecond on modern hardware, but the problem's explicit mandate for strictly disqualifies linear traversal. The values span , fitting comfortably inside standard 32-bit signed integers. Because target could be larger than every value, Lower Bound can return len(nums), so the search range is lo = 0 and hi = len(nums), and len(nums) must stay a possible answer.
The card's trap is reading nums[i] when i == len(nums): when every value is smaller than target, Lower Bound returns len(nums), and Python raises an IndexError. Check i < len(nums) before the look. At scale there is one more: the search is only as correct as the sort. If another thread inserts into or deletes from nums while you search, lo and hi can step past the target, so search a snapshot or hold a read lock.
Binary Search (LC 704)
nums is an integer array sorted in ascending order, and target is an integer; find where target sits in nums. Return that index if target is present, or -1 if it isn't.
Your algorithm must run in O(log n) time.
Worked Examples
nums = [-1,0,3,5,9,12], target = 94nums = [-1,0,3,5,9,12], target = 2-1⚖️Formal Constraints & Bounds
1 <= nums.length <= 104-104 < nums[i], target < 104All the integers in
numsare unique.numsis sorted in ascending order.
Core Insight
If target is in the sorted list, it is at the first index whose value is at least target. Lower Bound finds that index. One look at it answers the question.
Real-World Scenario & Production Applications
When looking up a record in an indexed B-Tree in PostgreSQL or searching an in-memory sorted cache, you never scan sequentially from the beginning. You jump to the middle, determine whether your key comes alphabetically or numerically before or after, and discard half the data space in a single CPU cycle.
Subproblems & Recurrence Decomposition3 Phases
Ask each index one yes-or-no question: nums[i] >= target. The answers are False before target's position and True from it on. Use the range [lo, hi) = [0, len(nums)), so len(nums) stays a possible answer.
# Check: False before target's position, True from it on
def at_least_target(i):
return nums[i] >= target
lo, hi = 0, len(nums)Step-by-Step Execution Trace Table
| Step | Range [lo, hi) | mid | nums[mid] | Check nums[mid] >= 9 | Decision | New range [lo, hi) |
|---|---|---|---|---|---|---|
| 1 | [0, 6) | 3 | 5 | False | 5 is smaller than 9, so the first True is after mid: lo = mid + 1 | [4, 6) |
| 2 | [4, 6) | 5 | 12 | True | mid may be the first True, so keep it: hi = mid | [4, 5) |
| 3 | [4, 5) | 4 | 9 | True | mid may be the first True, so keep it: hi = mid | [4, 4) |
| 4 | [4, 4) | The range is empty. Lower Bound returns i = 4. | ||||
| Look | nums[4] is 9 | 4 < len(nums) and nums[4] == 9 | Return index 4 |
| 1 | def at_least_target(i): |
| 2 | return nums[i] >= target |
| 3 | lo = 0 |
| 4 | hi = len(nums) |
| 5 | i = binary_search_lower_bound(lo, hi, at_least_target) |
| 6 | if i < len(nums) and nums[i] == target: |
| 7 | return i |
| 8 | return -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Exact Match asks whether a key is in a sorted list, and at which index. The answer is one look after a Lower Bound search. If the key is in the list, it sits at the first index whose value is at least the key. So find that index, and look at it.
🏟️ The Analogy: Opening an Alphabetized Physical Dictionary
Imagine looking up the word "Quasar" in a physical 2,000-page dictionary. You don't start at page 1 and read every word. You open the book roughly in the middle, landing on the letter "M". Since "Q" comes after "M", you instantly disregard pages 1 through 1,000 with your left hand. You then split the remaining pages 1,001 through 2,000 in half, landing on "T". Since "Q" comes before "T", you disregard pages 1,500 through 2,000. Each physical split discards hundreds of pages in constant time.
🔑 Why It Works
Every index before the first True holds a value smaller than the key, and the first True holds a value that is at least the key. If that value is equal to the key, it is the first copy. If it is larger, the key is not in the list. When every value is smaller, Lower Bound returns len(nums), and there is nothing to read, so the check i < len(nums) comes first.`,
Reading
nums[i]without checkingi < len(nums): Lower Bound returnslen(nums)when every value is smaller thantarget. There is no value at that index, sonums[i]raises anIndexError.Using
nums[i] == targetas the check: Lower Bound needs a row that reads False…False True…True. The row ofnums[i] == targetis True at one index only.Expecting any copy of
target: the template returns the first copy. The older closed-range loop returns the copy that it reaches first.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
You are given a sorted list and need the index of one value, or a sign that it is missing. The problem asks for better than O(N) time, so each step must remove half of the candidates.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: if target is in nums, it is at the first index whose value is at least target. The check nums[i] >= target is False for every index before that position and True from it on, so Lower Bound can find it. One look at that index then tells whether target is there.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Exact Match. The array is sorted, so the check nums[i] >= target is False before target's position and True from it on. I run Lower Bound over [0, len(nums)) with that check, and it returns the first index whose value is at least target. Then I look at that one index. If i < len(nums) and nums[i] == target, I return i. Otherwise I return -1. The trap is reading nums[i] when i equals len(nums), so I check the bound first. Lower Bound halves the range on every pass, so the time is
O(log n), and the space isO(1)."
Complexity & Mathematical Proof
O(log N)
Look at the loop in Lower Bound: while lo < hi:. Each pass computes mid and evaluates nums[mid] >= target in O(1). Then it keeps [lo, mid) or [mid + 1, hi), so the range loses at least half of its candidates. At most floor(log2 N) + 1 passes run (see the stages below). The final look at nums[i] is one comparison, so the total is O(log N) time.
O(1)
Look at the memory used: the loop is iterative, so the call stack holds one frame. Inside the function we store only the integers lo, hi, mid and i. We allocate no extra arrays, hash tables, or objects. Auxiliary space is O(1).
Derivation Progression
Window Size: N ⟹ N/2 ⟹ N/4 ⟹ ... ⟹ 1
The loop begins with a range of N candidates. Testing nums[mid] >= target removes half of the remaining candidates on every pass.
O(1) arithmetic + comparison
Calculating mid = lo + (hi - lo) // 2 and reading nums[mid] takes O(1) time, with no inner loop.
Total Steps = floor(log2 N) + 1 ⟹ O(log N)
Dividing N by 2 repeatedly reaches window width <= 1 in at most floor(log2 N) + 1 iterations.
Variable Definitions
Total number of elements in the sorted array
Memory Architecture & Bounds
O(1) Iterative while loop with zero recursion frames
O(1) Only scalar pointers (lo, hi, mid) in CPU registers
O(1) Returns a single integer index
Boundary Best / Worst Cases
— Lower Bound does not stop when it meets target, so even the best case runs every halving pass.
— Search requires approximately comparisons.
— Target is at the boundary leaf index or absent from the array.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
When I scan this problem statement, the immediate dead giveaways are the phrases "sorted in ascending order" and the explicit constraint the solution has to run in O(log n) time. A sorted array with unique elements where we are asked to find the index of a single target value is the canonical trigger for Exact Match. It tells me this is not a boundary or answer-space problem on its own. It is Lower Bound plus one look: the check nums[i] >= target is False before target's position and True from it on, so Lower Bound finds where target would go, and one look at that index tells me whether it is there.
The array length means an linear scan would technically execute in a fraction of a millisecond on modern hardware, but the problem's explicit mandate for strictly disqualifies linear traversal. The values span , fitting comfortably inside standard 32-bit signed integers. Because target could be larger than every value, Lower Bound can return len(nums), so the search range is lo = 0 and hi = len(nums), and len(nums) must stay a possible answer.
The card's trap is reading nums[i] when i == len(nums): when every value is smaller than target, Lower Bound returns len(nums), and Python raises an IndexError. Check i < len(nums) before the look. At scale there is one more: the search is only as correct as the sort. If another thread inserts into or deletes from nums while you search, lo and hi can step past the target, so search a snapshot or hold a read lock.