Skip to content

Volume ITechnology

4.11.0 — Binary Search: The Pattern ​

Recognition cue. The input is sorted, or the problem says O(\log n), or — the one people miss — it asks you to minimise the maximum, maximise the minimum, or find the smallest value such that something holds.

The move. Every step discards half the remaining possibilities.

The generalisation that matters. Binary search does not need an array. It needs a monotonic predicate: a yes/no question whose answer, once it flips from false to true, stays true. If you can phrase the problem that way, you can binary search it.

The two shapes ​

Almost every binary search is one of these. Deciding which one you are writing, before you write it, prevents nearly all boundary bugs.

python
# SHAPE A — find an exact element. "Bucket model": high is a real index.
low, high = 0, len(a) - 1  # (1)
while low <= high:                     # (2) a one-element range must still be checked
    mid = low + (high - low) # (3) 2
    if a[mid] == target: return mid  # (4)
    if a[mid] < target: low = mid + 1  # (5)
    else: high = mid - 1
return -1  # (6)

# SHAPE B — find a boundary. "Fence model": high is ONE PAST the end.
low, high = 0, len(a)                  # (7) n items have n+1 possible cut positions
while low < high:                      # (8) stop when the range collapses
    mid = low + (high - low) // 2
    if works(mid): high = mid          # (9) mid might be the answer — keep it
    else: low = mid + 1                # (10) mid is not — discard it
return low                             # (11) low == high == the boundary

The template, line by line.

(1) Shape A searches inside the list, so high is the last real position. (2) A range of one number still has to be checked, so loop while low <= high. (3) The middle, written so it cannot overflow in fixed-size languages. (4) Found the target. (5) The middle is too small, so the target can only be to its right; skip past mid. Otherwise it can only be to the left. (6) The range emptied without finding it.

(7) Shape B looks for the first position where a yes/no question turns to "yes". A list of n items has n + 1 such cut positions, so high starts one past the end. (8) Stop when the range shrinks to one position. (9) If mid works, it might be the answer, so keep it with high = mid. (10) If it does not work, nothing at or before it can be the answer, so move past it. (11) low and high meet on the first position that works.

Shape B never returns −1 and never tests for equality. It converges on a position. It is the shape for every "smallest value that works" problem, which is most of the hard ones.

The three rules that prevent every common bug ​

Compute mid as low + (high - low) // 2. Mathematically identical to (low + high) // 2, but it cannot overflow. This was a real bug in Java's standard library, unnoticed for nine years.

Never write low = mid. Integer division floors, so on a two-element range mid == low. Assigning low = mid leaves the range unchanged and the loop runs forever. Either advance past mid, or use shape B where the high = mid branch is the one that keeps it.

Match high to the loop condition. high = len - 1 goes with while low <= high. high = len goes with while low < high. Mixing them is the other half of all binary search bugs.

Binary search on the answer ​

When there is no array to search, search the space of possible answers. Three conditions:

  1. The answer is a number in a known range.
  2. "Does value X work?" is cheap to check.
  3. If X works, everything above it works too — or everything below, depending on direction.

The cost is O(\text{check} \times \log(\text{range})), and the log is over values, not array length. That is what makes it cheap even when the range is huge.

The seven problems ​

#ProblemThe one insight
4.11.1Binary SearchThe two shapes, and why mid is computed that way
4.11.2Search a 2D MatrixRows chain, so the grid is one sorted array
4.11.3Koko Eating BananasSearch the speed, not the array
4.11.4Find Minimum in Rotated Array ★Compare with nums[high], not nums[low]
4.11.5Search in Rotated Array ★One half is always cleanly sorted
4.11.6Time Based Key-Value StoreA floor search — largest key not exceeding the target
4.11.7Median of Two Sorted ArraysSearch for a cut, not a value

★ marks the Blind 75 subset.

The traps on this pattern ​

Missing the equality branch. In shape A, forgetting if a[mid] == target makes the search overshoot and return −1 on values that are present.

Seeding a tracker with index 0. In a floor search, initialise the answer to a sentinel that cannot be real data, not to the first element. "No valid entry" is a normal outcome.

Assuming the array is sorted when it is rotated. a[mid] < target no longer tells you the direction. Work out which half is clean first.

Duplicates. They break the rotated-array searches, because equal values at mid and the end carry no information. The fallback is to shrink by one, and the worst case becomes O(n). That degradation is unavoidable.

Floating point in ceiling division. math.ceil(p / k) converts to a float and loses precision at large magnitudes. Use (p + k - 1) // k.

What the interviewer will push on ​

"Why low + (high - low) // 2?" Overflow safety, and the Java story.

"Where does the infinite loop come from?" Floor division makes mid == low on a two-element range, so low = mid never advances.

"You have no sorted array — how can you binary search?" State the three conditions for binary search on the answer, then give the monotonic property in one sentence.

"Why do you search the shorter array in the median problem?" So the forced index into the other array cannot fall out of bounds.

"What happens with duplicates in a rotated array?" Linear worst case, and it cannot be avoided.

One thing to volunteer: say which shape you are writing before you write it. "This is a boundary search, so high starts one past the end and I never test for equality."

Recall

  • Binary search needs a monotonic predicate, not an array. "Once true, always true" is the requirement.
  • Shape A (bucket): high = n − 1, while low <= high, tests equality, returns −1 if absent.
  • Shape B (fence): high = n, while low < high, no equality test, converges on a position. This is the shape for "smallest value that works".
  • mid = low + (high − low) // 2 to avoid overflow. Never low = mid — floor division makes it an infinite loop.
  • Binary search on the answer when the problem says minimise the maximum, maximise the minimum, or smallest X such that. The log is over values, not array length.
  • Rotated array: compare nums[mid] with nums[high] to find the minimum; find the clean half to search for a target.
  • Duplicates destroy the log bound in rotated arrays; the fallback is to shrink by one, giving O(n).
  • A floor search returns the largest key at or below the target — remember the best candidate as you go, seeded with a sentinel.

Next: 4.11.1 Binary Search — the base case, written carefully enough that the six problems after it are assembly work.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet