What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

0. Binary Search Foundation & Monotonicity • Invariant Proof & Speed-Run

Theory Context•Binary Search Boundary

Conceptual Foundation & Intuitive Analogy

🏟️ The Analogy: The High-Low Number Guessing Game

Imagine guessing a secret number between 1 and 100. If your first guess is 50, and the host says "Too High!", you don't just know that 50 is wrong—you know that 51 through 100 are completely impossible. One question rules out 50 candidates. Your next guess is 25 (halfway between 1 and 49). If the host says "Too Low!", numbers 1 through 25 are ruled out. Within at most $\lceil \log_2(100) \rceil = 7$ questions, you are guaranteed to pin down the secret number out of 100 candidates. Binary search executes this exact elimination algorithm on computer memory.

🔑 Why It Works

The invariant that guarantees correctness is interval enclosure: at the start of every while-loop iteration, if target exists anywhere in nums, it is guaranteed to reside in nums[lo..hi]. When nums[mid] < target, the subarray nums[lo..mid] is strictly smaller than target, so advancing lo = mid + 1 preserves the enclosure without dropping the target.

Visual Blueprint & State Transition Model

Figure 1 • Binary Search Boundary Core Invariant & State Lifecycle

Core Invariant Specification

At every moment, if an answer exists at all, it lies inside [left, right]. Every branch We take preserves that.

Foundational Boundary Model Duality: Closed [L, R] vs Half-Open [L, R)

Closed Interval [L, R]while lo <= hi

Both L and R are inclusive valid indices. Candidate space shrinks symmetrically via lo = mid + 1 or hi = mid - 1. When lo == hi, exactly one candidate element remains to be inspected.

Primary Use: Standard Exact-Match (LC 704), 3-way branching, or recording candidate answers.

Half-Open Boundary [L, R)while lo < hi

R is an exclusive upper bound. Search space shrinks asymmetrically: hi = mid preserves the first valid candidate, while lo = mid + 1 discards the false prefix. Converges deterministically on lo == hi without post-loop adjustments.

Primary Use: Lower Bound / bisect_left (LC 35), Answer Space Bisection (LC 1011, LC 875).

The 2 Mental Models of Binary Search

Binary search applies whenever candidate feasibility is monotonic. Name the model before coding.

1Lower Bound

candidate domain ➔ monotonic boolean sequence [F, F, ..., T, T] ➔ first True

Lower Bound (First True Binary Search)

Spot it when: The statement asks for the first position or version that passes a test, such as where target would be inserted in a sorted list (Search Insert Position (LC 35)), the first bad version (First Bad Version (LC 278)), or the first value that is at least target.

Mode 1 · Lower Bound

Python

1	from typing import Callable, List
2
3
4	def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""First candidate in [lo, hi) where is_feasible is True.
6	Precondition: is_feasible is monotonic (False, False, ..., True, True).
7	Returns hi when no candidate is True. N = hi - lo candidates. T = the cost of one is_feasible call.
8	Time: O(T * log N) \| Space: O(1)
9	"""
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12
13	# 1. Check the Midpoint:
14	# is_feasible(mid) shows which side of the flip mid is on: before the answer (False),
15	# or at the answer or after it (True).
16	if is_feasible(mid):
17	# 2. Keep the Candidate:
18	# mid may be the first True, so keep it in the range by moving hi down to mid.
19	hi = mid
20	else:
21	# 3. Discard the Candidate:
22	# mid is False, so the first True must be strictly to the right of mid.
23	lo = mid + 1
24
25	# 4. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the first True, or hi when none was True.
27	return lo

is_feasible is False before the answer and True from the answer on, so one call at mid decides the move, which is hi = mid after a True and lo = mid + 1 after a False. A True mid may be the first True, so hi = mid keeps it in the range. A False mid is not the answer and the first True is to its right, so lo = mid + 1 drops it. After either move the first True is still in [lo, hi]. hi is allowed to be the answer, because it starts one past the last candidate, so a row with no True returns hi. The range gets smaller on every pass and lo never passes hi, so the loop stops with lo == hi, and lo is the answer. The trap is lo = mid in the False branch. The midpoint is rounded down, so when hi == lo + 1, mid equals lo. Then lo does not move, and the loop never ends.

Gotchas1 of 7

The trap
Gotcha 1: Writing lo = mid instead of lo = mid + 1
Mistake
```
lo = mid
```
Fix
```
lo = mid + 1
```
What happens: When one candidate is left (hi is equal to lo + 1), mid equals lo. If the check is False there, lo = mid leaves lo where it was. The range never gets smaller, so the loop never ends.
Example: Search Insert Position (LC 35): nums = [1, 3, 5, 6], target = 5
Mistake: the loop never endsFix: returns 2
Gotcha 2: Writing hi = mid - 1 in the half-open template
Mistake
```
hi = mid - 1
```
Fix
```
hi = mid
```
What happens: The template keeps mid in the range when the check is True, because mid may be the first True. With hi = mid - 1, a True mid is dropped. For nums = [1, 3, 5, 6] and target = 5, the first pass has mid = 2, and nums[2] >= 5 is True. Then hi becomes 1, so index 2 leaves the range. The loop returns 1, but the insert position is 2.
Example: Search Insert Position (LC 35): nums = [1, 3, 5, 6], target = 5
Mistake: returns 1Fix: returns 2
Gotcha 3: Setting hi to the last index, not one past it
Mistake
```
binary_search_lower_bound(0, len(nums) - 1, is_feasible)
```
Fix
```
binary_search_lower_bound(0, len(nums), is_feasible)
```
What happens: The loop can return hi itself. For Search Insert Position (LC 35), hi = len(nums) means "insert at the very end". With hi = len(nums) - 1, that answer can't be returned. A target larger than every value then gets the last index instead.
Example: nums = [1, 3, 5, 6], target = 7
Mistake: returns 3Fix: returns 4
Gotcha 4: Reading nums[i] without checking i < len(nums)
Mistake
```
found = nums[i] == target
```
Fix
```
found = i < len(nums) and nums[i] == target
```
What happens: The search returns the first True, or hi when no candidate is True. That result is not always a valid index. When no value passes the check, the result is len(nums). Reading nums[len(nums)] raises an IndexError. Find First and Last Position of Element in Sorted Array (LC 34) needs this check before it returns the first index.
Example: nums = [1, 3, 5, 6], target = 7
Mistake: raises IndexErrorFix: returns False
Gotcha 5: Using a check that is not monotonic
Mistake
```
is_feasible = lambda i: nums[i] == target
```
Fix
```
is_feasible = lambda i: nums[i] >= target
```
What happens: Binary search needs every False before every True. nums[i] == target is True at one index and False on both sides of it. The search can then discard the half that holds the answer.
Example: nums = [1, 3, 5, 6], target = 3
Mistake: returns 4Fix: returns 1
Gotcha 6: Adding 1 to what bisect_left returns
Mistake
```
count = bisect.bisect_left(a, x) + 1
```
Fix
```
count = bisect.bisect_left(a, x)
```
What happens: bisect.bisect_left(a, x) runs this search on a sorted list a. It returns the first index i with a[i] >= x. Indices start at 0, so that index is also the number of values less than x. Adding 1 counts one value too many. bisect.bisect_right(a, x) counts the values less than or equal to x in the same way.
Example: a = [1, 2, 2, 3], x = 2
Mistake: returns 2Fix: returns 1
Gotcha 7: Forgetting + lo on the bisect form
Mistake
```
first = bisect.bisect_left(range(lo, hi), True, key=is_feasible)
```
Fix
```
first = bisect.bisect_left(range(lo, hi), True, key=is_feasible) + lo
```
What happens: bisect_left returns an offset in range(lo, hi), counted from 0. It does not return an index. When lo is not 0, the offset and the index differ by lo. For lo = 2 and hi = 6, the first True is index 4, which is offset 2 in the range. Without + lo, the answer is 2.
Example: lo = 2, hi = 6, and the check is True from index 4 on
Mistake: returns 2Fix: returns 4

Canonical LeetCode:First Bad Version (LC 278)Search Insert Position (LC 35)Find First and Last Position of Element in Sorted Array (LC 34)Successful Pairs of Spells and Potions (LC 2300)Check If a Number Is Majority Element in a Sorted Array (LC 1150)Leftmost Column with at Least a One (LC 1428)Maximum Count of Positive Integer and Negative Integer (LC 2529)Fixed Point (LC 1064)Find K Closest Elements (LC 658)Single Element in a Sorted Array (LC 540)Count the Number of Fair Pairs (LC 2563)Longest Subsequence With Limited Sum (LC 2389)Ways to Split Array Into Three Subarrays (LC 1712)Missing Element in Sorted Array (LC 1060)Find Smallest Letter Greater Than Target (LC 744)H-Index II (LC 275)Time Based Key-Value Store (LC 981)Random Pick with Weight (LC 528)Random Point in Non-overlapping Rectangles (LC 497)

Open the Lower Bound card

2Upper Bound

candidate domain ➔ monotonic boolean sequence [T, T, ..., F, F] ➔ last True

Upper Bound (Last True Binary Search)

Spot it when: The statement asks for the largest value that still passes a test, or the last position that is at most a limit, such as the integer square root of x (Sqrt(x) (LC 69)) or the latest timestamp that is not after a given time (Time Based Key-Value Store (LC 981)).

Mode 2 · Upper Bound

Python

1	from typing import Callable
2
3
4	def binary_search_upper_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""Last candidate in [lo, hi) where is_feasible is True; lo - 1 when none is True."""
6	# lo becomes a known True, or the sentinel one before the first candidate; hi becomes the last candidate.
7	lo, hi = lo - 1, hi - 1
8
9	while lo < hi:
10	# 1. Compute the Ceiling Midpoint:
11	# Round mid up so lo < mid <= hi; rounding down would leave mid stuck at lo when one candidate remains.
12	mid = lo + (hi - lo + 1) // 2
13
14	# 2. Check the Midpoint:
15	# is_feasible(mid) shows which side of the flip mid is on: True at mid or before it, or False after it.
16	if is_feasible(mid):
17	# 3. Keep the Candidate:
18	# mid may be the last True, so keep it in the range by moving lo up to mid.
19	lo = mid
20	else:
21	# 4. Discard the Candidate:
22	# mid is False, so the last True must be strictly to the left of mid.
23	hi = mid - 1
24
25	# 5. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the last True, or the sentinel when none was True.
27	return lo

The check reads True…True False…False and the answer is the last True, so a True mid must stay in the range with lo = mid, and a False mid is dropped with hi = mid - 1. lo = mid can leave lo where it was, so the midpoint rounds up with mid = lo + (hi - lo + 1) // 2, which gives lo < mid <= hi. Then lo = mid always moves lo forward. The template first shifts both bounds down by 1 with lo, hi = lo - 1, hi - 1. After the shift, lo starts at the sentinel, which is the position lo - 1 just before the first candidate, and later holds a candidate that passed the check. hi starts at the last candidate. The sentinel is the value that the call returns when no candidate is True. The last True stays in [lo, hi] after both moves, and each move makes the range smaller, so the loop stops with lo == hi and returns lo. The trap is the rounded-down midpoint lo + (hi - lo) // 2 together with lo = mid. When hi == lo + 1, mid equals lo, a True check leaves lo where it was, and the loop never ends.

Gotchas1 of 7

The trap
Gotcha 1: Using the round-down midpoint with lo = mid
Mistake
```
mid = lo + (hi - lo) // 2
```
Fix
```
mid = lo + (hi - lo + 1) // 2
```
What happens: When two possible answers are left (lo and hi, with hi == lo + 1), lo + (hi - lo) // 2 is equal to lo. If the check is True there, lo = mid leaves lo where it was. The range does not become smaller, and the loop never ends. The round-up midpoint is always larger than lo.
Example: Sqrt(x) (LC 69): x = 8
Mistake: the loop never endsFix: returns 2
Gotcha 2: Writing hi = mid instead of hi = mid - 1
Mistake
```
hi = mid
```
Fix
```
hi = mid - 1
```
What happens: The round-up midpoint can be equal to hi. If the check is False there, hi = mid leaves hi where it was. The range does not become smaller, and the loop never ends. For a = [1, 2, 2, 3] and x = 2, the last pass has lo = 2 and hi = 3. Then mid is 3, the check a[3] <= 2 is False, and hi stays 3.
Example: a = [1, 2, 2, 3], x = 2
Mistake: the loop never endsFix: returns 2
Gotcha 3: Not shifting hi down by 1
Mistake
```
lo, hi = lo - 1, hi
```
Fix
```
lo, hi = lo - 1, hi - 1
```
What happens: The template moves hi down by 1 so that hi is the last candidate. Without the shift, hi is one past the last candidate. The round-up midpoint can then be equal to hi, and the check is called with a position that is not a candidate. For a = [5, 6, 7] and a check that is always True, the loop calls the check with index 3, and a[3] raises an IndexError.
Example: a = [5, 6, 7], and every value passes the check a[i] < 10
Mistake: raises IndexErrorFix: returns 2
Gotcha 4: Using Lower Bound's check nums[i] >= target
Mistake
```
is_feasible = lambda i: nums[i] >= target
```
Fix
```
is_feasible = lambda i: nums[i] <= target
```
What happens: Upper Bound needs a check that reads True…True False…False. nums[i] >= target reads False…False True…True, which is the row for Lower Bound. The search then follows the wrong side. For nums = [1, 3, 5, 6] and target = 3, the check is True from index 1 on, so every probe passes, the search keeps moving right, and it returns 3. The last index with nums[i] <= 3 is 1.
Example: nums = [1, 3, 5, 6], target = 3
Mistake: returns 3Fix: returns 1
Gotcha 5: Using the answer as an index without checking it
Mistake
```
value = a[answer]
```
Fix
```
value = a[answer] if answer >= 0 else None
```
What happens: When no candidate is True, the answer is -1. In Python, a[-1] does not raise an error. It reads the last value of the list, and the code continues with a wrong value. Check answer >= 0 before you read a[answer].
Example: a = [5, 6, 7], x = 3: no value is at most 3
Mistake: returns 7Fix: returns None
Gotcha 6: Using the last True index as a count
Mistake
```
count = last_index
```
Fix
```
count = last_index + 1
```
What happens: Indices start at 0. So the number of values up to the last True index is that index plus 1. For a = [1, 2, 2, 3] and x = 2, the last index with a[i] <= 2 is 2, and the count is 3.
Example: a = [1, 2, 2, 3], x = 2
Mistake: returns 2Fix: returns 3
Gotcha 7: Expecting bisect_right to find the last True
Mistake
```
last = bisect.bisect_right(a, x)
```
Fix
```
last = bisect.bisect_right(a, x) - 1
```
What happens: bisect_right finds the first index where a[i] > x. That is a first True, not a last True. For a = [1, 2, 2, 3] and x = 2, it returns 3. The last index with a[i] <= 2 is 2, so subtract 1.
Example: a = [1, 2, 2, 3], x = 2
Mistake: returns 3Fix: returns 2

Canonical LeetCode:Sqrt(x) (LC 69)Arranging Coins (LC 441)Find First and Last Position of Element in Sorted Array (LC 34)Time Based Key-Value Store (LC 981)

Open the Upper Bound card

Built on Lower Bound

Exact MatchClassic Binary Search
It asks Lower Bound for the first value that is at least target, and then checks whether that value is equal to target.
Extrema SearchPeak Finding (Bitonic Binary Search)
The check compares a value with the next value, so the search works on values that are not sorted, when they rise and then fall.
Rotated ArraySearch in Rotated Sorted Array
The check compares a value with the first value of the list, and it runs twice: once to find the pivot, and once to search the sorted order that starts at the pivot.
Feasible FunctionBinary Search on Answer (Parametric Search)
The candidates are possible answers, not positions in a list, and the check simulates the problem for one answer.
Kth SmallestBinary Search on Value Range (Kth Smallest in Sorted Matrix)
The check counts the values that are at most the candidate, and the answer is the smallest candidate whose count is at least k.
Median of Two Sorted ArraysPartition Binary Search (Median of Two Sorted Arrays)
The candidate is how many values to take from the shorter list, not a value, and the check compares the values on both sides of the cut.
Continuous BisectionBinary Search on Real Numbers (Bisection Method)
The candidates are real numbers, so the loop runs a fixed number of times instead of waiting until lo is equal to hi.
Global Matrix BisectionFlattened Index Binary Search (Search a 2D Matrix)
A row-major index maps to a matrix cell, and one guarded look confirms equality after Lower Bound.

The Binary Search Decision Rule

Which card do I need? Ask these questions in this order:

Step 1.Do you need the first value that passes a check, or the place where a value would be inserted?

➔ Lower Bound

First Bad Version (LC 278)Search Insert Position (LC 35)

Use the Lower Bound loop with a check that is False and then True.

Step 2.Do you only need to know whether a value is in a sorted list?

➔ Exact Match

Binary Search (LC 704)Guess Number Higher or Lower (LC 374)

Use Lower Bound to find the first value that is at least the target, then check whether that value is equal to the target.

Step 3.Do you need the largest value that still works?

➔ Upper Bound

Sqrt(x) (LC 69)Arranging Coins (LC 441)

Use Upper Bound with the ceiling midpoint; keep a passing mid and discard a failing mid.

Step 4.Is the list sorted, but rotated around a point you do not know?

➔ Rotated Array

Search in Rotated Sorted Array (LC 33)Find Minimum in Rotated Sorted Array (LC 153)

Find the pivot, the first value that is smaller than the first value of the list, and then search the sorted order that starts at the pivot.

Step 5.Do you need a peak in values that are not sorted?

➔ Extrema Search

Peak Index in a Mountain Array (LC 852)Find Peak Element (LC 162)

Compare each value with the next value. On a mountain the check is False then True; with several peaks, each update preserves some peak.

Step 6.Is the answer a number that you choose, and the check is a simulation of the problem?

➔ Feasible Function

Capacity To Ship Packages Within D Days (LC 1011)Koko Eating Bananas (LC 875)

Search the range of possible answers, and use the simulation as the check.

Step 7.Is the answer the k-th smallest value, and the check is a count of values?

➔ Kth Smallest

Kth Smallest Element in a Sorted Matrix (LC 378)Median of a Row Wise Sorted Matrix (LC 2387)

Search the range of values, and count how many values are at most the candidate.

Step 8.Do you need the median of two sorted lists?

➔ Median of Two Sorted Arrays

Median of Two Sorted Arrays (LC 4)

Search the place to cut the shorter list, and compare the values on both sides of the two cuts.

Step 9.Do sorted matrix rows continue one globally sorted list?

➔ Global Matrix Bisection

Search a 2D Matrix (LC 74)

Use Lower Bound on flat row-major indices and one guarded equality check.

Step 10.Is the answer a real number, accepted within a small error?

➔ Continuous Bisection

Separate Squares I (LC 3453)Minimize Max Distance to Gas Station (LC 774)

Run the loop a fixed number of times on real numbers, instead of waiting until `lo` is equal to `hi`.

Pattern Architecture & Invariant Design Masterclass

Binary search is not "an algorithm for finding a number in a sorted array." It is a decision procedure: you have a range of candidate answers, you can ask one yes/no question about the middle candidate, and the answer to that question is guaranteed to tell you which half of the range to throw away. Because you throw away half every time, a range of one million candidates is exhausted in about twenty questions instead of one million.

The one thing that must be true for this to work is monotonicity: as you move from left to right across the candidate range, the answer to your yes/no question flips from No to Yes exactly once and never flips back — [No, No, No, Yes, Yes, Yes]. If the answers can flip back and forth, discarding a half is unsound and the whole method collapses. Sortedness is just the most common way monotonicity shows up; it is not the requirement itself.

What an invariant is (this term recurs in every pattern, so it is worth one definition): an invariant is a statement that is true before the loop starts, still true after every single pass, and therefore true when the loop ends. It is how you prove code is right without running it — and in an interview, stating your invariant out loud is worth more than the code itself, because it shows you know why the algorithm terminates with the right answer rather than that you remember its shape.

Invariant-First Boundary Design (and the "Pair vs. Target" Heuristic)

Boundary conditions (< vs <=) and pointer shrinkage rules (mid ± 1 vs mid) are not arbitrary choices or keyword rules to memorize. In technical interviews, senior interviewers specifically test whether you can derive loop conditions directly from your candidate search space invariant:

1. Closed Candidate Space $[L, R]$ (`while left <= right:`)

The Invariant: At the start of every iteration, if a solution exists, it is guaranteed to lie in the closed index range [left, right].
The Halting Condition: The candidate set $\{x \mid \text{left} \le x \le \text{right}\}$ (closed candidate interval [left, right]) is non-empty whenever left <= right. When left == right, exactly one candidate element remains to be inspected (the singleton state).
When to Use: Standard Exact-Match Search (LC 704) where an immediate equality match triggers an early return, or where you shrink until left > right and return a sentinel if not found.

2. Half-Open Candidate Space $[L, R)$ (`while left < right:`)

The Invariant: The first True is in [left, right]: every index below left is False, and every index from right on is True or past the end. "Half-open" describes the indices still unchecked, [left, right): right itself is already known to be True (or past the end), so it stays in the answer range as the fallback, never excluded from it.
The Halting Condition: The loop runs while left < right because one candidate left (left == right) is already the answer, not because right is excluded. At termination, left (and right) points precisely to the boundary index without requiring post-loop fixups.
When to Use: Lower Bound / First Feasible Search (bisect_left, LC 35, LC 1011 Capacity to Ship Packages, LC 875 Koko Eating Bananas).
Cheat Sheet: positions vs. indices, why right = len(nums), and the bounds check before reading nums[left] are summarized in Algorithm Cheat Sheet → Binary Search Bounds.

3. Deconstructing "Target": Why the Term Can Mislead

"Target" is an overloaded term in algorithmic problems. Depending on what you are looking for, the invariant changes:

Exact-Match Target: Looking for a specific key value in an array $\rightarrow$ typically uses closed interval $[L, R]$ with left <= right and 3-way branching (==, <, >).
Insertion Point / Lower Bound Target: Finding the first index where nums[i] >= target $\rightarrow$ typically uses half-open $[L, R)$ with left < right and right = mid.
Boundary / Feasibility Target (Answer Space): Finding the minimum valid configuration (capacity, speed, days) where is_valid(mid) holds $\rightarrow$ uses monotonic predicate boundary search left < right with right = mid.

4. The "Pair vs. Target" Heuristic (Rule of Thumb)

The popular "Pair vs. Target" trick is a memorable starting heuristic, but it is not a universal law for pointer or binary-search loops:

The Heuristic: Developers often reach for < when needing a pair of distinct elements (Two Sum II, Valid Palindrome) because left == right is degenerate, and <= when testing a target in a closed candidate space so the final singleton is examined.
Why It Is Not Universal: Correct boundary conditions depend on the precise invariant, whether endpoints are inclusive $[L, R]$ or exclusive $[L, R)$ , whether a problem needs the first/last valid position or an exact match, and the update rules for left, right, and mid. For instance, lower-bound and feasibility searches evaluate targets with while left < right and right = mid without post-processing, while 3-way Dutch National Flag partitioning inspects elements with while mid <= high.
Senior Formulation: State your candidate invariant first: "I am maintaining the candidate answer in [left, right]. Since the candidate set is non-empty whenever left <= right, my loop condition is while left <= right:, and my updates are mid + 1 and mid - 1."

Common Questions

"Binary search is for finding a value in a sorted array. So how does it apply to something like minimizing the maximum ship capacity (LC 1011), where there's no sorted array of capacities to search at all?"

Because sortedness was never the actual requirement — it's just the most familiar disguise of the real one, monotonicity.

Standard search asks "is nums[mid] too small, too big, or exactly the target?" — three outcomes, and the array's sortedness is what guarantees discarding a half is safe. But binary search only ever needs one yes/no question whose answer flips exactly once as you scan the candidate range: [No, No, No, Yes, Yes, Yes]. A sorted array happens to produce that pattern for "is nums[mid] >= target?" — but so does an entirely invented, unsorted range of candidate answers, as long as the yes/no question you ask about them is monotonic.

For "ship packages within D days," the array of package weights is never binary-searched — it's a fixed input, sorted or not. What gets binary-searched is an invented range of possible ship capacities, from max(weights) to sum(weights). The question can_ship(mid) ("can a ship of capacity mid finish in D days or fewer?") is monotonic: every capacity below the true minimum answers No, every capacity at or above it answers Yes. That single monotonic predicate is the whole requirement — which is why the same algorithm also solves Koko Eating Bananas and Split Array Largest Sum, none of which involve searching a sorted array of anything.

Coach discussion points

1.
"What exactly makes this array searchable in O(log n)? Give me the predicate and prove it never flips back." — Tests whether the student has internalised monotonicity or has merely memorised "sorted array → binary search".
2.
"You wrote while lo <= hi and hi = mid. Walk me through lo == hi and tell me what happens." — Forces the student to discover the infinite loop by tracing rather than being told.
3.
"In the capacity problem you said O(log n). What is n, and what does one iteration actually cost?" — Probes whether the predicate's own O(n) cost was multiplied in. This is the single highest-signal follow-up in this pattern.
4.
"You have found a match on the first probe and you are about to return. Under what version of this question would returning now be a bug?" — Surfaces the duplicates/boundary distinction, and the difference between "found one" and "found the first".
5.
"In the median-of-two-sorted-arrays solution, why do you always binary search the SHORTER array? What changes if you search the longer one instead?" — Tests whether the student understands j = half - i is a forced arithmetic consequence, not an independent choice, and that searching the shorter array only lowers the cost, from O(log max(m, n)) to O(log min(m, n)). The range [max(0, k - n), min(m, k) + 1) keeps every read inside both lists for either order.
6.
"Walk me through why x - arr[mid] > arr[mid + k] - x is monotonic across window left-edges, when neither side is compared to a fixed target." — Probes whether the student can identify monotonicity in a relative, window-shift comparison rather than only in the more familiar "compare to a fixed value" shape.
7.
"In Search a 2D Matrix you wrote divmod(mid, n). Which number is n, and what would divmod(mid, m) read on a 3 x 4 grid?" — Makes the student find the row-count bug by tracing one flat index, instead of being told that a square test hides it.
8.
"Search a 2D Matrix II (LC 240) also has sorted rows. Why does the same flat-index search give wrong answers there?" — Tests whether the student knows the flat index needs each row to start after the previous one ends, not just sorted rows.
9.
"In Sqrt(x) you wrote lo = mid when the check passes. Trace x = 4 from lo = 2, hi = 3 with mid = lo + (hi - lo) // 2. What happens, and what one-character change fixes it?" — Makes the student find the floor-midpoint infinite loop of Upper Bound (last True) by tracing, and see why the midpoint must round up once a passing mid is kept with lo = mid.
10.
"C++ calls its 'first value greater than target' search upper_bound. Is that a first True or a last True, and how would you get the last index whose value is at most target?" — Separates the library name from the model: upper_bound / bisect_right is a Lower Bound (first True) search; the last index <= target is that minus one, or an Upper Bound search.
11.
"In Separate Squares I, lo and hi are two floats with nothing between them. What does (lo + hi) / 2 give, and what does while lo < hi do from there?" — Makes the student find the float infinite loop of Continuous Bisection by reasoning about one round, and see why the loop must count rounds.
12.
"In K-th Smallest Prime Fraction you have hi after 100 rounds, but the answer must be a pair. Which fraction do you return, and why can no other fraction be between it and hi?" — Tests the snap: the final window is narrower than the smallest gap between two fractions, about 1 / (3 * 10⁴)^2.
13.
"In Find Minimum in Rotated Sorted Array II, nums[mid] == nums[hi]. Is mid in the left run or the right one? Show me an array for each answer." — Makes the student build [1, 1, 1, 0, 1] and [1, 0, 1, 1, 1] and see that a tie picks no side, so it can only drop hi.
14.
"Why is dropping hi on a tie safe, and what does that step cost when every value is equal? Can any algorithm do better?" — Tests the invariant (a copy of nums[hi] stays at mid) and the $O(n)$ lower bound: with 1s and one hidden 0, every unread index could hold the 0.

Complexity analysis

Time: O(log n). Each iteration replaces the live interval with one of its halves, so after k iterations at most n / 2^k candidates remain. The loop ends when that reaches 1, i.e. when k = log₂ n. Formally T(n) = T(n/2) + O(1), which by the Master Theorem (case 2, a = 1, b = 2, f(n) = O(1)) gives Θ(log n). Concretely: 1,000,000 candidates need at most 20 questions. 1,000,000,000 need at most 30.

Where that changes: in archetype 4.4 the predicate is not O(1) — it is an O(n) greedy scan. Total cost is therefore O(n · log(sum - max)), not O(log n). Students routinely quote O(log n) here and are wrong; the interviewer is checking whether you multiplied by the predicate's own cost.

Space: O(1). The iterative form holds exactly three integers (lo, hi, mid) plus one accumulator. No allocation, no recursion. The recursive form is O(log n) because each halving pushes a stack frame — a real, if small, difference worth naming aloud.

Production Systems Deployment & Motivation

You are looking up the word "monotone" in a 1,000-page paper dictionary. You do not start at page 1 and turn pages one at a time. You open the book near the middle, land on page 500, read the first word on it, and see it starts with "L". "M" comes after "L", so you have just eliminated pages 1-500 without reading a single one of them. You then repeat on pages 501-1000.

The same shape runs inside real systems every day:

A PostgreSQL B-Tree index descends toward a row id by comparing keys and discarding subtrees.
A deployment tool bisecting a broken build (git bisect) halves the commit range on each "is it broken here? yes/no".
A capacity planner asking "can 2 machines finish this workload in <= T minutes?" and shrinking T.

Mastery Roadmap & Prerequisite Graph

💡 Don't worry if boundary decisions feel subtle right now! Binary search is one fundamental bisection principle applied across monotonic domains. As you progress through the 9 Archetype Variants (from Exact Match and Rotated Minimum to Capacity Allocation and Median of Two Sorted Arrays), each hands-on challenge will cement this intuition until choosing between lo <= hi vs lo < hi and writing hi = mid - 1 vs hi = mid becomes second nature.

Integer overflow on midpoint calculation: In 32-bit environments (Java/C++/C#), (left + right) // 2 overflows when left + right > 2³¹ - 1. Always calculate midpoint as left + (right - left) // 2.
Infinite loop via unreduced interval (left = mid): When right - left = 1, integer division floors mid to left. Assigning left = mid fails to shrink the search space, looping forever. Use left = mid + 1 or half-open intervals.
Applying binary search to unsorted inputs: Binary search fundamentally requires a monotonic predicate. Applying it to an unsorted or partially sorted list produces arbitrary incorrect results with no warning.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "sorted order", "monotonic predicate f(x) -> bool", "minimize the maximum / maximize the minimum", "O(log N) runtime budget". Binary search is fundamentally not about looking up numbers in arrays; it is the algorithmic exploitation of monotonicity to eliminate half the remaining candidate solution space in $O(1)$ decision steps.

CONSTRAINTS & BOUNDS

Discrete search space size $N$ up to $10^{18}$ (answer space bisection), or array index boundaries $[0, N-1]$ up to $10^9$ . A logarithmic time budget $O(\log N)$ allows traversing an astronomical $2^{60}$ element space in at most 60 predicate evaluations. Space budget is strictly $O(1)$ registers.

FAANG PRODUCTION TRAPS & EDGE CASES

Three classic pitfalls: (1) Integer overflow when computing midpoint $(lo + hi) // 2$ in 32-bit systems (mitigate via $lo + (hi - lo) // 2$ ); (2) Off-by-one infinite loops caused by mismatched loop conditions (while lo < hi vs while lo <= hi) with incorrect boundary assignments; (3) Failure to establish a strictly monotonic boolean predicate.

Theory Context•Binary Search Boundary

Conceptual Foundation & Intuitive Analogy

🏟️ The Analogy: The High-Low Number Guessing Game

🔑 Why It Works

Visual Blueprint & State Transition Model

Figure 1 • Binary Search Boundary Core Invariant & State Lifecycle

Core Invariant Specification

At every moment, if an answer exists at all, it lies inside [left, right]. Every branch We take preserves that.

Foundational Boundary Model Duality: Closed [L, R] vs Half-Open [L, R)

Closed Interval [L, R]while lo <= hi

Both L and R are inclusive valid indices. Candidate space shrinks symmetrically via lo = mid + 1 or hi = mid - 1. When lo == hi, exactly one candidate element remains to be inspected.

Primary Use: Standard Exact-Match (LC 704), 3-way branching, or recording candidate answers.

Half-Open Boundary [L, R)while lo < hi

Primary Use: Lower Bound / bisect_left (LC 35), Answer Space Bisection (LC 1011, LC 875).

The 2 Mental Models of Binary Search

Binary search applies whenever candidate feasibility is monotonic. Name the model before coding.

1Lower Bound

candidate domain ➔ monotonic boolean sequence [F, F, ..., T, T] ➔ first True

Lower Bound (First True Binary Search)

Mode 1 · Lower Bound

Python

1	from typing import Callable, List
2
3
4	def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""First candidate in [lo, hi) where is_feasible is True.
6	Precondition: is_feasible is monotonic (False, False, ..., True, True).
7	Returns hi when no candidate is True. N = hi - lo candidates. T = the cost of one is_feasible call.
8	Time: O(T * log N) \| Space: O(1)
9	"""
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12
13	# 1. Check the Midpoint:
14	# is_feasible(mid) shows which side of the flip mid is on: before the answer (False),
15	# or at the answer or after it (True).
16	if is_feasible(mid):
17	# 2. Keep the Candidate:
18	# mid may be the first True, so keep it in the range by moving hi down to mid.
19	hi = mid
20	else:
21	# 3. Discard the Candidate:
22	# mid is False, so the first True must be strictly to the right of mid.
23	lo = mid + 1
24
25	# 4. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the first True, or hi when none was True.
27	return lo

Gotchas1 of 7

The trap
Gotcha 1: Writing lo = mid instead of lo = mid + 1
Mistake
```
lo = mid
```
Fix
```
lo = mid + 1
```
What happens: When one candidate is left (hi is equal to lo + 1), mid equals lo. If the check is False there, lo = mid leaves lo where it was. The range never gets smaller, so the loop never ends.
Example: Search Insert Position (LC 35): nums = [1, 3, 5, 6], target = 5
Mistake: the loop never endsFix: returns 2
Gotcha 2: Writing hi = mid - 1 in the half-open template
Mistake
```
hi = mid - 1
```
Fix
```
hi = mid
```
What happens: The template keeps mid in the range when the check is True, because mid may be the first True. With hi = mid - 1, a True mid is dropped. For nums = [1, 3, 5, 6] and target = 5, the first pass has mid = 2, and nums[2] >= 5 is True. Then hi becomes 1, so index 2 leaves the range. The loop returns 1, but the insert position is 2.
Example: Search Insert Position (LC 35): nums = [1, 3, 5, 6], target = 5
Mistake: returns 1Fix: returns 2
Gotcha 3: Setting hi to the last index, not one past it
Mistake
```
binary_search_lower_bound(0, len(nums) - 1, is_feasible)
```
Fix
```
binary_search_lower_bound(0, len(nums), is_feasible)
```
What happens: The loop can return hi itself. For Search Insert Position (LC 35), hi = len(nums) means "insert at the very end". With hi = len(nums) - 1, that answer can't be returned. A target larger than every value then gets the last index instead.
Example: nums = [1, 3, 5, 6], target = 7
Mistake: returns 3Fix: returns 4
Gotcha 4: Reading nums[i] without checking i < len(nums)
Mistake
```
found = nums[i] == target
```
Fix
```
found = i < len(nums) and nums[i] == target
```
What happens: The search returns the first True, or hi when no candidate is True. That result is not always a valid index. When no value passes the check, the result is len(nums). Reading nums[len(nums)] raises an IndexError. Find First and Last Position of Element in Sorted Array (LC 34) needs this check before it returns the first index.
Example: nums = [1, 3, 5, 6], target = 7
Mistake: raises IndexErrorFix: returns False
Gotcha 5: Using a check that is not monotonic
Mistake
```
is_feasible = lambda i: nums[i] == target
```
Fix
```
is_feasible = lambda i: nums[i] >= target
```
What happens: Binary search needs every False before every True. nums[i] == target is True at one index and False on both sides of it. The search can then discard the half that holds the answer.
Example: nums = [1, 3, 5, 6], target = 3
Mistake: returns 4Fix: returns 1
Gotcha 6: Adding 1 to what bisect_left returns
Mistake
```
count = bisect.bisect_left(a, x) + 1
```
Fix
```
count = bisect.bisect_left(a, x)
```
What happens: bisect.bisect_left(a, x) runs this search on a sorted list a. It returns the first index i with a[i] >= x. Indices start at 0, so that index is also the number of values less than x. Adding 1 counts one value too many. bisect.bisect_right(a, x) counts the values less than or equal to x in the same way.
Example: a = [1, 2, 2, 3], x = 2
Mistake: returns 2Fix: returns 1
Gotcha 7: Forgetting + lo on the bisect form
Mistake
```
first = bisect.bisect_left(range(lo, hi), True, key=is_feasible)
```
Fix
```
first = bisect.bisect_left(range(lo, hi), True, key=is_feasible) + lo
```
What happens: bisect_left returns an offset in range(lo, hi), counted from 0. It does not return an index. When lo is not 0, the offset and the index differ by lo. For lo = 2 and hi = 6, the first True is index 4, which is offset 2 in the range. Without + lo, the answer is 2.
Example: lo = 2, hi = 6, and the check is True from index 4 on
Mistake: returns 2Fix: returns 4

Open the Lower Bound card

2Upper Bound

candidate domain ➔ monotonic boolean sequence [T, T, ..., F, F] ➔ last True

Upper Bound (Last True Binary Search)

Mode 2 · Upper Bound

Python

1	from typing import Callable
2
3
4	def binary_search_upper_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""Last candidate in [lo, hi) where is_feasible is True; lo - 1 when none is True."""
6	# lo becomes a known True, or the sentinel one before the first candidate; hi becomes the last candidate.
7	lo, hi = lo - 1, hi - 1
8
9	while lo < hi:
10	# 1. Compute the Ceiling Midpoint:
11	# Round mid up so lo < mid <= hi; rounding down would leave mid stuck at lo when one candidate remains.
12	mid = lo + (hi - lo + 1) // 2
13
14	# 2. Check the Midpoint:
15	# is_feasible(mid) shows which side of the flip mid is on: True at mid or before it, or False after it.
16	if is_feasible(mid):
17	# 3. Keep the Candidate:
18	# mid may be the last True, so keep it in the range by moving lo up to mid.
19	lo = mid
20	else:
21	# 4. Discard the Candidate:
22	# mid is False, so the last True must be strictly to the left of mid.
23	hi = mid - 1
24
25	# 5. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the last True, or the sentinel when none was True.
27	return lo

Gotchas1 of 7

The trap
Gotcha 1: Using the round-down midpoint with lo = mid
Mistake
```
mid = lo + (hi - lo) // 2
```
Fix
```
mid = lo + (hi - lo + 1) // 2
```
What happens: When two possible answers are left (lo and hi, with hi == lo + 1), lo + (hi - lo) // 2 is equal to lo. If the check is True there, lo = mid leaves lo where it was. The range does not become smaller, and the loop never ends. The round-up midpoint is always larger than lo.
Example: Sqrt(x) (LC 69): x = 8
Mistake: the loop never endsFix: returns 2
Gotcha 2: Writing hi = mid instead of hi = mid - 1
Mistake
```
hi = mid
```
Fix
```
hi = mid - 1
```
What happens: The round-up midpoint can be equal to hi. If the check is False there, hi = mid leaves hi where it was. The range does not become smaller, and the loop never ends. For a = [1, 2, 2, 3] and x = 2, the last pass has lo = 2 and hi = 3. Then mid is 3, the check a[3] <= 2 is False, and hi stays 3.
Example: a = [1, 2, 2, 3], x = 2
Mistake: the loop never endsFix: returns 2
Gotcha 3: Not shifting hi down by 1
Mistake
```
lo, hi = lo - 1, hi
```
Fix
```
lo, hi = lo - 1, hi - 1
```
What happens: The template moves hi down by 1 so that hi is the last candidate. Without the shift, hi is one past the last candidate. The round-up midpoint can then be equal to hi, and the check is called with a position that is not a candidate. For a = [5, 6, 7] and a check that is always True, the loop calls the check with index 3, and a[3] raises an IndexError.
Example: a = [5, 6, 7], and every value passes the check a[i] < 10
Mistake: raises IndexErrorFix: returns 2
Gotcha 4: Using Lower Bound's check nums[i] >= target
Mistake
```
is_feasible = lambda i: nums[i] >= target
```
Fix
```
is_feasible = lambda i: nums[i] <= target
```
What happens: Upper Bound needs a check that reads True…True False…False. nums[i] >= target reads False…False True…True, which is the row for Lower Bound. The search then follows the wrong side. For nums = [1, 3, 5, 6] and target = 3, the check is True from index 1 on, so every probe passes, the search keeps moving right, and it returns 3. The last index with nums[i] <= 3 is 1.
Example: nums = [1, 3, 5, 6], target = 3
Mistake: returns 3Fix: returns 1
Gotcha 5: Using the answer as an index without checking it
Mistake
```
value = a[answer]
```
Fix
```
value = a[answer] if answer >= 0 else None
```
What happens: When no candidate is True, the answer is -1. In Python, a[-1] does not raise an error. It reads the last value of the list, and the code continues with a wrong value. Check answer >= 0 before you read a[answer].
Example: a = [5, 6, 7], x = 3: no value is at most 3
Mistake: returns 7Fix: returns None
Gotcha 6: Using the last True index as a count
Mistake
```
count = last_index
```
Fix
```
count = last_index + 1
```
What happens: Indices start at 0. So the number of values up to the last True index is that index plus 1. For a = [1, 2, 2, 3] and x = 2, the last index with a[i] <= 2 is 2, and the count is 3.
Example: a = [1, 2, 2, 3], x = 2
Mistake: returns 2Fix: returns 3
Gotcha 7: Expecting bisect_right to find the last True
Mistake
```
last = bisect.bisect_right(a, x)
```
Fix
```
last = bisect.bisect_right(a, x) - 1
```
What happens: bisect_right finds the first index where a[i] > x. That is a first True, not a last True. For a = [1, 2, 2, 3] and x = 2, it returns 3. The last index with a[i] <= 2 is 2, so subtract 1.
Example: a = [1, 2, 2, 3], x = 2
Mistake: returns 3Fix: returns 2

Canonical LeetCode:Sqrt(x) (LC 69)Arranging Coins (LC 441)Find First and Last Position of Element in Sorted Array (LC 34)Time Based Key-Value Store (LC 981)

Open the Upper Bound card

Built on Lower Bound

Exact MatchClassic Binary Search
It asks Lower Bound for the first value that is at least target, and then checks whether that value is equal to target.
Extrema SearchPeak Finding (Bitonic Binary Search)
The check compares a value with the next value, so the search works on values that are not sorted, when they rise and then fall.
Rotated ArraySearch in Rotated Sorted Array
The check compares a value with the first value of the list, and it runs twice: once to find the pivot, and once to search the sorted order that starts at the pivot.
Feasible FunctionBinary Search on Answer (Parametric Search)
The candidates are possible answers, not positions in a list, and the check simulates the problem for one answer.
Kth SmallestBinary Search on Value Range (Kth Smallest in Sorted Matrix)
The check counts the values that are at most the candidate, and the answer is the smallest candidate whose count is at least k.
Median of Two Sorted ArraysPartition Binary Search (Median of Two Sorted Arrays)
The candidate is how many values to take from the shorter list, not a value, and the check compares the values on both sides of the cut.
Continuous BisectionBinary Search on Real Numbers (Bisection Method)
The candidates are real numbers, so the loop runs a fixed number of times instead of waiting until lo is equal to hi.
Global Matrix BisectionFlattened Index Binary Search (Search a 2D Matrix)
A row-major index maps to a matrix cell, and one guarded look confirms equality after Lower Bound.

The Binary Search Decision Rule

Which card do I need? Ask these questions in this order:

Step 1.Do you need the first value that passes a check, or the place where a value would be inserted?

➔ Lower Bound

First Bad Version (LC 278)Search Insert Position (LC 35)

Use the Lower Bound loop with a check that is False and then True.

Step 2.Do you only need to know whether a value is in a sorted list?

➔ Exact Match

Binary Search (LC 704)Guess Number Higher or Lower (LC 374)

Use Lower Bound to find the first value that is at least the target, then check whether that value is equal to the target.

Step 3.Do you need the largest value that still works?

➔ Upper Bound

Sqrt(x) (LC 69)Arranging Coins (LC 441)

Use Upper Bound with the ceiling midpoint; keep a passing mid and discard a failing mid.

Step 4.Is the list sorted, but rotated around a point you do not know?

➔ Rotated Array

Search in Rotated Sorted Array (LC 33)Find Minimum in Rotated Sorted Array (LC 153)

Find the pivot, the first value that is smaller than the first value of the list, and then search the sorted order that starts at the pivot.

Step 5.Do you need a peak in values that are not sorted?

➔ Extrema Search

Peak Index in a Mountain Array (LC 852)Find Peak Element (LC 162)

Compare each value with the next value. On a mountain the check is False then True; with several peaks, each update preserves some peak.

Step 6.Is the answer a number that you choose, and the check is a simulation of the problem?

➔ Feasible Function

Capacity To Ship Packages Within D Days (LC 1011)Koko Eating Bananas (LC 875)

Search the range of possible answers, and use the simulation as the check.

Step 7.Is the answer the k-th smallest value, and the check is a count of values?

➔ Kth Smallest

Kth Smallest Element in a Sorted Matrix (LC 378)Median of a Row Wise Sorted Matrix (LC 2387)

Search the range of values, and count how many values are at most the candidate.

Step 8.Do you need the median of two sorted lists?

➔ Median of Two Sorted Arrays

Median of Two Sorted Arrays (LC 4)

Search the place to cut the shorter list, and compare the values on both sides of the two cuts.

Step 9.Do sorted matrix rows continue one globally sorted list?

➔ Global Matrix Bisection

Search a 2D Matrix (LC 74)

Use Lower Bound on flat row-major indices and one guarded equality check.

Step 10.Is the answer a real number, accepted within a small error?

➔ Continuous Bisection

Separate Squares I (LC 3453)Minimize Max Distance to Gas Station (LC 774)

Run the loop a fixed number of times on real numbers, instead of waiting until `lo` is equal to `hi`.

Pattern Architecture & Invariant Design Masterclass

Invariant-First Boundary Design (and the "Pair vs. Target" Heuristic)

1. Closed Candidate Space $[L, R]$ (`while left <= right:`)

The Invariant: At the start of every iteration, if a solution exists, it is guaranteed to lie in the closed index range [left, right].
The Halting Condition: The candidate set $\{x \mid \text{left} \le x \le \text{right}\}$ (closed candidate interval [left, right]) is non-empty whenever left <= right. When left == right, exactly one candidate element remains to be inspected (the singleton state).
When to Use: Standard Exact-Match Search (LC 704) where an immediate equality match triggers an early return, or where you shrink until left > right and return a sentinel if not found.

2. Half-Open Candidate Space $[L, R)$ (`while left < right:`)

The Invariant: The first True is in [left, right]: every index below left is False, and every index from right on is True or past the end. "Half-open" describes the indices still unchecked, [left, right): right itself is already known to be True (or past the end), so it stays in the answer range as the fallback, never excluded from it.
The Halting Condition: The loop runs while left < right because one candidate left (left == right) is already the answer, not because right is excluded. At termination, left (and right) points precisely to the boundary index without requiring post-loop fixups.
When to Use: Lower Bound / First Feasible Search (bisect_left, LC 35, LC 1011 Capacity to Ship Packages, LC 875 Koko Eating Bananas).
Cheat Sheet: positions vs. indices, why right = len(nums), and the bounds check before reading nums[left] are summarized in Algorithm Cheat Sheet → Binary Search Bounds.

3. Deconstructing "Target": Why the Term Can Mislead

"Target" is an overloaded term in algorithmic problems. Depending on what you are looking for, the invariant changes:

Exact-Match Target: Looking for a specific key value in an array $\rightarrow$ typically uses closed interval $[L, R]$ with left <= right and 3-way branching (==, <, >).
Insertion Point / Lower Bound Target: Finding the first index where nums[i] >= target $\rightarrow$ typically uses half-open $[L, R)$ with left < right and right = mid.
Boundary / Feasibility Target (Answer Space): Finding the minimum valid configuration (capacity, speed, days) where is_valid(mid) holds $\rightarrow$ uses monotonic predicate boundary search left < right with right = mid.

4. The "Pair vs. Target" Heuristic (Rule of Thumb)

The popular "Pair vs. Target" trick is a memorable starting heuristic, but it is not a universal law for pointer or binary-search loops:

The Heuristic: Developers often reach for < when needing a pair of distinct elements (Two Sum II, Valid Palindrome) because left == right is degenerate, and <= when testing a target in a closed candidate space so the final singleton is examined.
Why It Is Not Universal: Correct boundary conditions depend on the precise invariant, whether endpoints are inclusive $[L, R]$ or exclusive $[L, R)$ , whether a problem needs the first/last valid position or an exact match, and the update rules for left, right, and mid. For instance, lower-bound and feasibility searches evaluate targets with while left < right and right = mid without post-processing, while 3-way Dutch National Flag partitioning inspects elements with while mid <= high.
Senior Formulation: State your candidate invariant first: "I am maintaining the candidate answer in [left, right]. Since the candidate set is non-empty whenever left <= right, my loop condition is while left <= right:, and my updates are mid + 1 and mid - 1."

Common Questions

"Binary search is for finding a value in a sorted array. So how does it apply to something like minimizing the maximum ship capacity (LC 1011), where there's no sorted array of capacities to search at all?"

Because sortedness was never the actual requirement — it's just the most familiar disguise of the real one, monotonicity.

Standard search asks "is nums[mid] too small, too big, or exactly the target?" — three outcomes, and the array's sortedness is what guarantees discarding a half is safe. But binary search only ever needs one yes/no question whose answer flips exactly once as you scan the candidate range: [No, No, No, Yes, Yes, Yes]. A sorted array happens to produce that pattern for "is nums[mid] >= target?" — but so does an entirely invented, unsorted range of candidate answers, as long as the yes/no question you ask about them is monotonic.

For "ship packages within D days," the array of package weights is never binary-searched — it's a fixed input, sorted or not. What gets binary-searched is an invented range of possible ship capacities, from max(weights) to sum(weights). The question can_ship(mid) ("can a ship of capacity mid finish in D days or fewer?") is monotonic: every capacity below the true minimum answers No, every capacity at or above it answers Yes. That single monotonic predicate is the whole requirement — which is why the same algorithm also solves Koko Eating Bananas and Split Array Largest Sum, none of which involve searching a sorted array of anything.

Coach discussion points

1.
"What exactly makes this array searchable in O(log n)? Give me the predicate and prove it never flips back." — Tests whether the student has internalised monotonicity or has merely memorised "sorted array → binary search".
2.
"You wrote while lo <= hi and hi = mid. Walk me through lo == hi and tell me what happens." — Forces the student to discover the infinite loop by tracing rather than being told.
3.
"In the capacity problem you said O(log n). What is n, and what does one iteration actually cost?" — Probes whether the predicate's own O(n) cost was multiplied in. This is the single highest-signal follow-up in this pattern.
4.
"You have found a match on the first probe and you are about to return. Under what version of this question would returning now be a bug?" — Surfaces the duplicates/boundary distinction, and the difference between "found one" and "found the first".
5.
"In the median-of-two-sorted-arrays solution, why do you always binary search the SHORTER array? What changes if you search the longer one instead?" — Tests whether the student understands j = half - i is a forced arithmetic consequence, not an independent choice, and that searching the shorter array only lowers the cost, from O(log max(m, n)) to O(log min(m, n)). The range [max(0, k - n), min(m, k) + 1) keeps every read inside both lists for either order.
6.
"Walk me through why x - arr[mid] > arr[mid + k] - x is monotonic across window left-edges, when neither side is compared to a fixed target." — Probes whether the student can identify monotonicity in a relative, window-shift comparison rather than only in the more familiar "compare to a fixed value" shape.
7.
"In Search a 2D Matrix you wrote divmod(mid, n). Which number is n, and what would divmod(mid, m) read on a 3 x 4 grid?" — Makes the student find the row-count bug by tracing one flat index, instead of being told that a square test hides it.
8.
"Search a 2D Matrix II (LC 240) also has sorted rows. Why does the same flat-index search give wrong answers there?" — Tests whether the student knows the flat index needs each row to start after the previous one ends, not just sorted rows.
9.
"In Sqrt(x) you wrote lo = mid when the check passes. Trace x = 4 from lo = 2, hi = 3 with mid = lo + (hi - lo) // 2. What happens, and what one-character change fixes it?" — Makes the student find the floor-midpoint infinite loop of Upper Bound (last True) by tracing, and see why the midpoint must round up once a passing mid is kept with lo = mid.
10.
"C++ calls its 'first value greater than target' search upper_bound. Is that a first True or a last True, and how would you get the last index whose value is at most target?" — Separates the library name from the model: upper_bound / bisect_right is a Lower Bound (first True) search; the last index <= target is that minus one, or an Upper Bound search.
11.
"In Separate Squares I, lo and hi are two floats with nothing between them. What does (lo + hi) / 2 give, and what does while lo < hi do from there?" — Makes the student find the float infinite loop of Continuous Bisection by reasoning about one round, and see why the loop must count rounds.
12.
"In K-th Smallest Prime Fraction you have hi after 100 rounds, but the answer must be a pair. Which fraction do you return, and why can no other fraction be between it and hi?" — Tests the snap: the final window is narrower than the smallest gap between two fractions, about 1 / (3 * 10⁴)^2.
13.
"In Find Minimum in Rotated Sorted Array II, nums[mid] == nums[hi]. Is mid in the left run or the right one? Show me an array for each answer." — Makes the student build [1, 1, 1, 0, 1] and [1, 0, 1, 1, 1] and see that a tie picks no side, so it can only drop hi.
14.
"Why is dropping hi on a tie safe, and what does that step cost when every value is equal? Can any algorithm do better?" — Tests the invariant (a copy of nums[hi] stays at mid) and the $O(n)$ lower bound: with 1s and one hidden 0, every unread index could hold the 0.

Complexity analysis

Production Systems Deployment & Motivation

The same shape runs inside real systems every day:

A PostgreSQL B-Tree index descends toward a row id by comparing keys and discarding subtrees.
A deployment tool bisecting a broken build (git bisect) halves the commit range on each "is it broken here? yes/no".
A capacity planner asking "can 2 machines finish this workload in <= T minutes?" and shrinking T.

Mastery Roadmap & Prerequisite Graph

Integer overflow on midpoint calculation: In 32-bit environments (Java/C++/C#), (left + right) // 2 overflows when left + right > 2³¹ - 1. Always calculate midpoint as left + (right - left) // 2.
Infinite loop via unreduced interval (left = mid): When right - left = 1, integer division floors mid to left. Assigning left = mid fails to shrink the search space, looping forever. Use left = mid + 1 or half-open intervals.
Applying binary search to unsorted inputs: Binary search fundamentally requires a monotonic predicate. Applying it to an unsorted or partially sorted list produces arbitrary incorrect results with no warning.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Conceptual Foundation & Intuitive Analogy

🏟️ The Analogy: The High-Low Number Guessing Game

🔑 Why It Works

The 2 Mental Models of Binary Search

1Lower Bound

2Upper Bound

Built on Lower Bound

The Binary Search Decision Rule

Pattern Architecture & Invariant Design Masterclass

Invariant-First Boundary Design (and the "Pair vs. Target" Heuristic)

1. Closed Candidate Space [L,R][L, R][L,R] (while left <= right:)

2. Half-Open Candidate Space [L,R)[L, R)[L,R) (while left < right:)

3. Deconstructing "Target": Why the Term Can Mislead

4. The "Pair vs. Target" Heuristic (Rule of Thumb)

Common Questions

Coach discussion points

Complexity analysis

Staff+ Systems Architecture & Hardware Considerations

Conceptual Foundation & Intuitive Analogy

🏟️ The Analogy: The High-Low Number Guessing Game

🔑 Why It Works

The 2 Mental Models of Binary Search

1Lower Bound

2Upper Bound

Built on Lower Bound

The Binary Search Decision Rule

Pattern Architecture & Invariant Design Masterclass

Invariant-First Boundary Design (and the "Pair vs. Target" Heuristic)

1. Closed Candidate Space [L,R][L, R][L,R] (while left <= right:)

2. Half-Open Candidate Space [L,R)[L, R)[L,R) (while left < right:)

3. Deconstructing "Target": Why the Term Can Mislead

4. The "Pair vs. Target" Heuristic (Rule of Thumb)

Common Questions

Coach discussion points

Complexity analysis

Staff+ Systems Architecture & Hardware Considerations

1. Closed Candidate Space $[L, R]$ (`while left <= right:`)

2. Half-Open Candidate Space $[L, R)$ (`while left < right:`)

1. Closed Candidate Space $[L, R]$ (`while left <= right:`)

2. Half-Open Candidate Space $[L, R)$ (`while left < right:`)