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 magic or rigid keyword rules. 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 left le x le right}$ is non-empty whenever left <= right. When left == right, exactly one candidate element remains to be inspected (the singleton state).
• The Update Rules: Because the loop body evaluates nums[mid] directly (e.g. if nums[mid] == target: return mid), mid has been thoroughly inspected. If it doesn't match, we must shrink both sides past mid: left = mid + 1 or right = mid - 1.
• 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 target or boundary value is guaranteed to lie in the half-open range [left, right), where right is an exclusive upper bound.
• The Halting Condition: The candidate set is non-empty as long as left < right. When left == right, the interval [left, left) has length zero (empty candidate set), and the loop terminates naturally. At termination, left (and right) points precisely to the boundary index without requiring post-loop fixups.
• The Update Rules: If feasible(mid) is true (or nums[mid] >= target), mid could be the minimal valid answer. Since right is exclusive, setting right = mid keeps mid inside the candidate space! If feasible(mid) is false, mid is eliminated, so left = mid + 1.
• When to Use: Lower Bound / First Feasible Search (bisect_left, LC 35, LC 1011 Capacity to Ship Packages, LC 875 Koko Eating Bananas).

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 $o$ 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 $o$ 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 $o$ 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 le right$, my loop condition is while left <= right:, and my updates are mid + 1 and mid - 1."