settings: look: preset: blueprint steps: - title: "Binary Search | Find anything in sorted data, fast" stepType: intro narration: > A million sorted records, and you need one of them. Binary search finds it in about twenty comparisons. This lesson shows exactly how, and where people get it wrong. - title: "The Phone Book Problem" stepType: explanation content: | Nobody finds a name by reading every page. You open in the middle and throw half the book away. Binary search is that habit, written down precisely. narration: > Think of a paper phone book. You never start at page one. You open near the middle, see which half the name is in, and ignore the other half. - title: "What Is at Stake" stepType: stats content: | 1,000,000 | comparisons in the worst case, scanning one by one 20 | comparisons with binary search on the same data narration: > On a million items, a simple scan may need a million comparisons. Binary search needs twenty. That gap is the whole reason this algorithm matters. - title: "01 | The slow way" stepType: banner narration: > Before the fast method, look closely at the slow one. Seeing what it wastes is the quickest way to understand what binary search saves. - title: "Scan From the Left" stepType: viz narration: > Here are fifteen sorted numbers. The target is fifty six. A linear scan starts at index zero and checks each value in turn. viz: canvas: grid padding: 64 caption: "Target: 56. Start at index 0." state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { i: 0 } highlight: { "0": compare } transition: auto - title: "One Value at a Time" stepType: viz narration: > Six comparisons in, the scan has reached twenty six. Each comparison ruled out exactly one value, and nine candidates are still waiting. viz: canvas: grid padding: 64 caption: compare: { left: 26, op: "<", right: 56, leftLabel: current, rightLabel: target, hint: "keep walking" } state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { i: 5 } highlight: { "0": eliminated, "1": eliminated, "2": eliminated, "3": eliminated, "4": eliminated, "5": compare } transition: auto - title: "Found, Eventually" stepType: viz narration: > The scan finally lands on fifty six at index ten. It took eleven comparisons, and it would take a million on a million items. viz: canvas: grid padding: 64 caption: "Found 56 at index 10 after 11 comparisons" state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { i: 10 } dim: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] highlight: { "10": found } transition: auto - title: "What the Scan Ignores" stepType: explanation content: | The scan never uses the fact that the data is sorted. Every comparison answers one question about one value, and nothing more. narration: > The scan works on any list, sorted or not. That is its weakness here. It throws away the most useful fact we have: the values are in order. - title: "02 | The idea" stepType: banner narration: > Now use the order. In sorted data, one well placed comparison can answer a question about half the list at once. - title: "One Comparison, Half the List" stepType: explanation content: | Look at the middle value. If it is too small, so is everything to its left. One comparison just ruled out half the data. narration: > Pick the middle value. If it is smaller than the target, every value to its left is smaller too. They can all be discarded without being read. - title: "Start With the Whole Range" stepType: viz narration: > Two pointers mark the range that could still hold the target. Low starts at index zero and high at index fourteen, so every value is a candidate. viz: canvas: grid padding: 64 caption: "Target: 56. Every index is still a candidate." state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { lo: 0, hi: 14 } transition: auto - title: "Check the Middle" stepType: viz narration: > The middle of zero and fourteen is index seven, which holds thirty five. Thirty five is smaller than fifty six, so the target must be to the right. viz: canvas: grid padding: 64 caption: compare: { left: 35, op: "<", right: 56, leftLabel: middle, rightLabel: target, hint: "discard the left half" } state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { lo: 0, mid: 7, hi: 14 } highlight: { "7": compare } transition: auto - title: "Throw Half Away" stepType: viz narration: > Low jumps to index eight, one past the middle. Eight values vanish from the search after a single comparison. Seven candidates remain. viz: canvas: grid padding: 64 caption: "lo = mid + 1. Seven candidates remain." state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { lo: 8, hi: 14 } dim: [0, 1, 2, 3, 4, 5, 6, 7] transition: auto - title: "What One Comparison Bought" stepType: compare content: | Linear scan | Binary search Rules out 1 value | Rules out 8 values 14 candidates left | 7 candidates left Ignores the order | Uses the order narration: > Compare the first step of each method. The scan removed one candidate. Binary search removed eight, because the order did the work. - title: "Check the New Middle" stepType: viz narration: > Repeat on the smaller range. The middle of eight and fourteen is index eleven, holding sixty three. That is larger than fifty six. viz: canvas: grid padding: 64 caption: compare: { left: 63, op: ">", right: 56, leftLabel: middle, rightLabel: target, hint: "discard the right half" } state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { lo: 8, mid: 11, hi: 14 } dim: [0, 1, 2, 3, 4, 5, 6, 7] highlight: { "11": compare } transition: auto - title: "Shrink From the Right" stepType: viz narration: > This time high moves, to index ten, one before the middle. Only three candidates are left: forty two, forty nine, and fifty six. viz: canvas: grid padding: 64 caption: "hi = mid - 1. Three candidates remain." state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { lo: 8, hi: 10 } dim: [0, 1, 2, 3, 4, 5, 6, 7, 11, 12, 13, 14] transition: auto - title: "Zoom Into What Is Left" stepType: viz narration: > The middle of eight and ten is index nine, holding forty nine. Smaller than the target again, so low moves past it. viz: canvas: grid padding: 64 caption: compare: { left: 49, op: "<", right: 56, leftLabel: middle, rightLabel: target, hint: "discard the left part" } state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { lo: 8, mid: 9, hi: 10 } dim: [0, 1, 2, 3, 4, 5, 6, 7, 11, 12, 13, 14] highlight: { "9": compare } camera: { fit: region, region: { from: 6, to: 12 } } transition: auto - title: "The Rhythm" stepType: list content: | 1. Look at the middle of the range 2. Compare it with the target 3. Discard the half that cannot hold it 4. Repeat on what is left narration: > Notice the rhythm. Look at the middle, compare, discard half, repeat. Nothing else happens in binary search. Every round is these four moves. - title: "Found" stepType: viz narration: > Low and high now both point at index ten. The middle is index ten, and it holds fifty six. The search is over. viz: canvas: grid padding: 64 caption: "Found 56 at index 10 after 4 comparisons" state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { lo: 10, mid: 10, hi: 10 } dim: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14] highlight: { "10": found } timeline: - at: 20 effect: { type: pulse, target: 10, frames: 14, intensity: 2 } transition: auto - title: "Same Answer, Less Work" stepType: stats content: | 11 | comparisons, linear scan 4 | comparisons, binary search 15 | values in the list narration: > Both methods found index ten. The scan needed eleven comparisons and binary search needed four. The gap grows quickly as the list grows. - title: "03 | Writing it" stepType: banner narration: > The picture is clear. Now turn it into code, one decision at a time, so every line has a reason you can point to in the picture. - title: "Two Pointers" stepType: code language: python code: | def binary_search(items, target): lo, hi = 0, len(items) - 1 narration: > Start with the two pointers from the picture. Low is the first index and high is the last, so the range covers the whole list. - title: "Loop While Candidates Remain" stepType: code language: python code: | def binary_search(items, target): lo, hi = 0, len(items) - 1 while lo <= hi: mid = (lo + hi) // 2 narration: > Keep going while the range is not empty. Inside the loop, compute the middle index with integer division. - title: "The Lucky Case" stepType: code language: python code: | def binary_search(items, target): lo, hi = 0, len(items) - 1 while lo <= hi: mid = (lo + hi) // 2 if items[mid] == target: return mid narration: > If the middle value is the target, return its index immediately. This is the only place the function reports success. - title: "Too Small: Go Right" stepType: code language: python code: | def binary_search(items, target): lo, hi = 0, len(items) - 1 while lo <= hi: mid = (lo + hi) // 2 if items[mid] == target: return mid if items[mid] < target: lo = mid + 1 narration: > Otherwise discard a half. If the middle value is too small, the target can only be to the right, so low moves one past the middle. - title: "Discard a Half" stepType: code language: python code: | def binary_search(items, target): lo, hi = 0, len(items) - 1 while lo <= hi: mid = (lo + hi) // 2 if items[mid] == target: return mid if items[mid] < target: lo = mid + 1 else: hi = mid - 1 narration: > And if it is too large, high moves one before the middle. Either way, the middle itself never stays in the range. - title: "Run It" stepType: cli narration: > Run it on the list from the picture, looking for fifty six. Found at index ten, in four comparisons. cli: username: dev hostname: laptop commands: - pwd: ~/search command: python search.py 56 output: - "index 10 (4 comparisons)" status: success - title: "And a Value That Is Missing" stepType: cli narration: > Now ask for fifty, which is not in the list. It still stops after four comparisons. Next we watch how. cli: username: dev hostname: laptop commands: - pwd: ~/search command: python search.py 56 output: - "index 10 (4 comparisons)" status: success - pwd: ~/search command: python search.py 50 output: - "not found (4 comparisons)" status: success - title: "04 | When the target is missing" stepType: banner narration: > A search has to end even when there is nothing to find. Watch what the pointers do when the target is not in the list. - title: "Searching for Fifty" stepType: viz narration: > Search for fifty. The first two comparisons go exactly as before and leave the same three candidates between index eight and ten. viz: canvas: grid padding: 64 caption: "Target: 50. Three candidates remain." state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { lo: 8, hi: 10 } dim: [0, 1, 2, 3, 4, 5, 6, 7, 11, 12, 13, 14] transition: auto - title: "Too Small, Then Too Large" stepType: viz narration: > Forty nine is too small, so low moves to ten. Now the only candidate is fifty six, and fifty six is larger than fifty. viz: canvas: grid padding: 64 caption: compare: { left: 56, op: ">", right: 50, leftLabel: middle, rightLabel: target, hint: "discard it too" } state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { lo: 10, mid: 10, hi: 10 } dim: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14] highlight: { "10": compare } transition: auto - title: "The Pointers Cross" stepType: viz narration: > High moves to nine while low stays at ten. Low is now greater than high. The range is empty, the loop ends, and the answer is not found. viz: canvas: grid padding: 64 caption: "lo > hi. The range is empty: return -1." state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { hi: 9, lo: 10 } dim: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] highlight: { "9": eliminated, "10": eliminated } transition: auto - title: "Finish the Function" stepType: code language: python code: | def binary_search(items, target): lo, hi = 0, len(items) - 1 while lo <= hi: ... # compare, then discard a half return -1 # the pointers crossed narration: > That is the last line of the function. When the loop ends without a return, the pointers have crossed, so the target is not there. - title: "05 | Three bugs everyone writes" stepType: banner narration: > Binary search is famous for being easy to describe and hard to get right. Three small mistakes cause almost all of the broken versions. - title: "Bug One: The Loop Condition" stepType: compare content: | while lo < hi | while lo <= hi Stops with one candidate unchecked | Checks a range of one Misses targets at the edges | Finds every target narration: > The first bug is the loop condition. With less than, the loop stops while one candidate is still unchecked. Less than or equal checks it. - title: "Bug Two: Not Moving Past the Middle" stepType: code language: python code: | while lo <= hi: mid = (lo + hi) // 2 if items[mid] < target: lo = mid # bug: should be mid + 1 else: hi = mid - 1 narration: > The second bug keeps the middle in the range. It looks harmless, but the middle has already been checked and must be excluded. - title: "Why That Loops Forever" stepType: viz narration: > With low at nine and high at ten, the middle is nine. Setting low to the middle changes nothing. The range never shrinks and the loop never ends. viz: canvas: grid padding: 64 caption: "lo = mid leaves lo at 9. The range never shrinks." state: values: [3, 8, 12, 17, 21, 26, 31, 35, 42, 49, 56, 63, 71, 78, 86] pointers: { lo: 9, mid: 9, hi: 10 } dim: [0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 14] highlight: { "9": compare } timeline: - at: 24 effect: { type: shake, target: 9, frames: 12, intensity: 3 } transition: auto - title: "Bug Three: Overflow" stepType: code language: java code: | // Overflows when lo + hi exceeds the int range int mid = (lo + hi) / 2; narration: > The third bug hides in languages with fixed width integers. On a very large array, low plus high can exceed what an int holds. - title: "The Safe Midpoint" stepType: code language: java code: | // Overflows when lo + hi exceeds the int range // int mid = (lo + hi) / 2; // Safe: the difference always fits int mid = lo + (hi - lo) / 2; narration: > So that line goes, commented out here. Never add the two. Take half the distance between them, and add that to low. Same midpoint, no overflow. - title: "Before You Trust It" stepType: checklist content: | - [x] The input is sorted - [x] The loop runs while lo <= hi - [x] Both bounds move past the middle - [ ] Tested with a missing target - [ ] Tested with one item, and with none narration: > Use this whenever you review a binary search. Sorted input, the right loop condition, bounds that move past the middle. Then two tests you must write. A missing target, and lists of one item and none. - title: "06 | Why it is fast" stepType: banner narration: > Twenty comparisons for a million items sounds like magic. It is just halving, and the arithmetic is short enough to do in your head. - title: "Halve Until One Is Left" stepType: latex narration: > Each comparison halves the range. After k comparisons, n items have become n over two to the k. The search ends when that reaches one. latex: title: "How many halvings?" formulas: - '\frac{n}{2^{k}} = 1' - 'k = \log_2 n' - title: "Growth of the Two Methods" stepType: chart narration: > Plot the worst case for both. The scan climbs in step with the data. The binary search line barely leaves the floor. chart: type: echarts id: comparisons-by-size ariaLabel: Line chart of worst case comparisons for linear scan and binary search as the list grows option: title: text: "Worst case comparisons" subtext: "By number of items in the list" legend: data: [Linear scan, Binary search] xAxis: type: category boundaryGap: false data: ["16", "64", "128", "256", "512", "1024"] yAxis: type: value series: - id: linear name: Linear scan type: line symbolSize: 14 data: [16, 64, 128, 256, 512, 1024] - id: binary name: Binary search type: line symbolSize: 14 data: [4, 6, 7, 8, 9, 10] label: show: true position: top - title: "Three Sizes to Remember" stepType: stats content: | 10 | comparisons for a thousand items 20 | comparisons for a million 30 | comparisons for a billion narration: > Three numbers are worth remembering. Ten comparisons for a thousand items, twenty for a million, and thirty for a billion. - title: "Doubling Costs One Step" stepType: explanation content: | Double the data, and binary search needs **one** more comparison. narration: > Here is the practical meaning. When the data doubles, a scan does twice the work. Binary search does one extra comparison. - title: "07 | The version you will actually use" stepType: banner narration: > Real code rarely asks whether a value is present. It asks where a value belongs. A small change to the algorithm answers that question. - title: "A Better Question" stepType: compare content: | Is it there? | Where does it belong? Returns an index or -1 | Returns the first index not less than the target Any matching copy | Always the leftmost copy Useless for inserting | Exactly where to insert narration: > The new question is: what is the first position whose value is not less than the target? It is called the lower bound, and it handles duplicates. - title: "Duplicates in the Data" stepType: viz narration: > This list holds three fours. We want the first one. Here high starts one past the end, because the answer may be the end of the list. viz: canvas: grid padding: 64 caption: "Target: 4. lo = 0, and hi = 8, one past the last index." state: values: [2, 4, 4, 4, 7, 9, 9, 12] pointers: { lo: 0, hi: 8 } transition: cut - title: "Keep the Middle as a Candidate" stepType: viz narration: > The middle is index four, holding seven. Seven is not less than four, so index four could be the answer. High moves to it, not past it. viz: canvas: grid padding: 64 caption: compare: { left: 7, op: "≥", right: 4, leftLabel: middle, rightLabel: target, hint: "hi = mid" } state: values: [2, 4, 4, 4, 7, 9, 9, 12] pointers: { lo: 0, mid: 4, hi: 8 } highlight: { "4": compare } transition: cut - title: "The Rule That Changed" stepType: explanation content: | Never return early. A match is only a candidate, because an earlier copy may exist. narration: > This is the one real difference. We never return on a match. A match stays in the range as a candidate while we keep looking to its left. - title: "Closing In From the Right" stepType: viz narration: > The middle of zero and four is index two, holding four. Not less than the target, so high moves to two. Then index one, by the same rule. viz: canvas: grid padding: 64 caption: compare: { left: 4, op: "≥", right: 4, leftLabel: middle, rightLabel: target, hint: "hi = mid" } state: values: [2, 4, 4, 4, 7, 9, 9, 12] pointers: { lo: 0, mid: 2, hi: 4 } dim: [4, 5, 6, 7] highlight: { "2": compare } transition: cut - title: "The First Four" stepType: viz narration: > At index zero the value is two, which is less than four, so low moves to one. Low and high meet at index one: the first four. viz: canvas: grid padding: 64 caption: "lo == hi == 1. The first 4 is at index 1." state: values: [2, 4, 4, 4, 7, 9, 9, 12] pointers: { lo: 1, hi: 1 } dim: [0, 2, 3, 4, 5, 6, 7] highlight: { "1": found } timeline: - at: 20 effect: { type: pulse, target: 1, frames: 14, intensity: 2 } transition: cut - title: "A Wider Starting Range" stepType: code language: python code: | def lower_bound(items, target): lo, hi = 0, len(items) narration: > Now as code. One difference on the second line. High starts at the length, one past the last index, because the answer may be the very end. - title: "Until They Meet" stepType: code language: python code: | def lower_bound(items, target): lo, hi = 0, len(items) while lo < hi: mid = (lo + hi) // 2 narration: > The loop runs while low is strictly less than high. It ends when they meet, not when they cross. - title: "Too Small Still Goes Right" stepType: code language: python code: | def lower_bound(items, target): lo, hi = 0, len(items) while lo < hi: mid = (lo + hi) // 2 if items[mid] < target: lo = mid + 1 narration: > A middle value that is too small is handled exactly as before. Low moves past it. - title: "Otherwise Keep the Middle" stepType: code language: python code: | def lower_bound(items, target): lo, hi = 0, len(items) while lo < hi: mid = (lo + hi) // 2 if items[mid] < target: lo = mid + 1 else: hi = mid narration: > Here is the rule that changed. Otherwise high becomes the middle itself, not one before it. The middle might be the answer. - title: "Lower Bound in Code" stepType: code language: python code: | def lower_bound(items, target): lo, hi = 0, len(items) while lo < hi: mid = (lo + hi) // 2 if items[mid] < target: lo = mid + 1 else: hi = mid return lo narration: > When they meet, that position is the answer. Return low. There is no early return and no minus one. - title: "Where You Have Already Used It" stepType: list content: | - Database indexes finding a row by key - Autocomplete finding where a prefix starts - Package managers finding the newest allowed version - git bisect finding the commit that broke a build narration: > You use binary search every day without seeing it. Database indexes, autocomplete, version resolution, and one you can run yourself, git bisect. - title: "Start a Bisect" stepType: cli narration: > Tell git one commit that is bad and one that was good. Five hundred commits lie between them, and it expects nine steps. cli: username: dev hostname: laptop commands: - pwd: ~/app command: git bisect start HEAD v2.0 output: - "Bisecting: 511 revisions left to test after this (roughly 9 steps)" status: success - title: "Binary Search Over History" stepType: cli narration: > Hand it your test command. Git checks out the middle commit, runs the tests, discards half, and repeats until it names the culprit. cli: username: dev hostname: laptop commands: - pwd: ~/app command: git bisect start HEAD v2.0 output: - "Bisecting: 511 revisions left to test after this (roughly 9 steps)" status: success - pwd: ~/app command: git bisect run npm test output: - "a1c9f02 is the first bad commit" status: success - title: "08 | Recap" stepType: banner narration: > That is the whole algorithm, its failure modes, and its most useful variant. Here is what to carry away. - title: "What to Remember" stepType: list content: | 1. It only works on sorted data 2. Each comparison discards half the range 3. Lower bound answers where a value belongs narration: > Three things. The data must be sorted. Each comparison discards half. And lower bound tells you where a value belongs. - title: "Your Turn" stepType: outro content: | A sorted list has 4,000 items. What is the most comparisons binary search can need? Answer: 12, because 2 to the power 12 is 4,096. narration: > Try this before you go. A sorted list has four thousand items. What is the largest number of comparisons binary search could need to finish?