Synthesis: which pattern to use?
Two modules, five patterns. Time to train the reflex: glance at a statement and know whether it's binary search, which flavor, or whether it's a bit problem — with justification.
The section's decision tree
1. Is the data SORTED (or is there a monotonic "no→yes" boundary)?
├── search for an exact value → classic BINARY SEARCH
├── SORTED but ROTATED array → modified binary search
│ (which half is sorted?)
├── "first/last that satisfies..." → BOUNDARY binary search
└── "the SMALLEST/LARGEST x that works" → binary search ON THE ANSWER
(testing a candidate x is O(n))
2. Does the problem mention BITS, binary, or have a strange space constraint?
├── "appears 2x except one" / "missing" → XOR (pairs cancel out)
├── count/look at/turn on/clear bits → operators & | ^ ~ << >>
├── "for each i, count the bits" → counting bits (ans[i]=ans[i>>1]+(i&1))
└── "without using +", reverse bits → techniques (carry via &<<1, mirror)
And the usual sanity check: if the statement asks for better than O(n) on sorted data, it's almost certain the answer is O(log n) — binary search.
The section's complete map
| Pattern | Key question | Time | Space |
|---|---|---|---|
| Classic binary search | "find a value in a sorted array" | O(log n) | O(1) |
| Rotated binary search | "sorted and rotated array" | O(log n) | O(1) |
| Search on the answer | "smallest/largest x that satisfies" | O(n log(range)) | O(1) |
| XOR | "appears 2x except one / missing" | O(n) | O(1) |
| Bit operators | test/turn on/clear/count bits | O(1)–O(width) | O(1) |
| Counting bits | "1 bits of 0..n" | O(n) | O(n) (output) |
The idea that unites the binary search module: discard half with certainty at each step. The one that unites the bits module: operate on the 0s and 1s directly, instead of treating the number as a quantity.
Section quiz
Statements you haven't seen in the lessons. Identify the pattern and the why. 7+ correct: ready for the exam.
🧠 Section quiz: Binary
0/81. 'In a sorted array, find the position where a target should be inserted to keep it sorted.' Which pattern?
2. 'Given an array where every number appears 3x, except one that appears 1x, find the loner.' Does simple XOR solve it?
3. 'What's the smallest capacity of a ship to carry all the packages in D days?' Which pattern?
4. 'Find the peak (an element greater than its neighbors) in O(log n).' Why does binary search work even without the array being sorted?
5. 'Detect whether an integer is a power of 2.' Which bit technique solves it in O(1)?
6. What is the GENERAL condition for using binary search, as seen in this section?
7. Why is XOR preferable to the 'Gauss sum' for finding a missing number?
8. What's the master idea that unites the binary search MODULE?
Ready for the exam?
The final exam for the Binary section has three brand-new problems — easy, medium and hard — with hidden cases. The hard one applies binary search on the answer (the flavor from the decision tree that might be the most surprising). The five lessons cover everything you need.
Good luck! Go back to the section page and click "Final exam".