"I'm thinking of a number between 1 and 100. Guess it." What do you do? You don't start at 1 and work your way up. You don't guess randomly. You say **50**. Too high? Okay, now you know it's between 1 and 49. You say **25**. Too low? Now it's between 26 and 49. Each guess **cuts the possibilities in half**. Congratulations — you already understand binary search. You've been doing it your whole life. Looking up a word in a dictionary? Binary search. Finding a name in a phone book? Binary search. Scrolling through a sorted playlist to find a song? Binary search. The trick is learning to see it in code problems, even when it's not obvious. That's what this guide is about. --- ## The Big Idea: Why O(log n) is a Superpower Before we write a single line of code, let's talk about why binary search matters so much. **Linear search** checks every element one by one. If you have a billion items, that's a billion steps. Not great. **Binary search** cuts the search space in half with every step. If you have a billion items, that's about **30 steps**. Yes, thirty. > Let that sink in: 1,000,000,000 items → ~30 steps. That's the power of O(log n). Here's the math behind it. Each step halves the space, so you're asking: "How many times can I divide n by 2 before I get to 1?" That's the definition of log₂(n). | Items (n) | Linear Search Steps | Binary Search Steps | |-----------|--------------------|--------------------| | 100 | 100 | ~7 | | 10,000 | 10,000 | ~14 | | 1,000,000 | 1,000,000 | ~20 | | 1,000,000,000 | 1,000,000,000 | ~30 | That's not just faster — it's a completely different universe of performance. And it's why binary search shows up constantly in interviews, system design, and real-world algorithms. --- ## Classic Binary Search: The Foundation Let's start with the textbook version. You have a **sorted array** and a **target value**. Find the target's index, or return -1 if it doesn't exist. ### The Concept Place a pointer at the **left** end and another at the **right** end. Look at the **middle** element: - If it's the target — done! - If the target is smaller — search the left half - If the target is larger — search the right half Repeat until you find it or the pointers cross. ### TypeScript Implementation ```typescript function binarySearch(nums: number[], target: number): number { let left = 0; let right = nums.length - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } ``` ### Step-by-Step Walkthrough Let's trace through `binarySearch([1, 3, 5, 7, 9, 11, 13], 9)`: ``` Step 1: left=0, right=6, mid=3 → nums[3]=7 < 9 → search right half Step 2: left=4, right=6, mid=5 → nums[5]=11 > 9 → search left half Step 3: left=4, right=4, mid=4 → nums[4]=9 === 9 → found at index 4! ``` Three steps to find our target in a 7-element array. A linear scan might have taken up to 7. ### Why `left + Math.floor((right - left) / 2)` Instead of `Math.floor((left + right) / 2)`? Both give the same result mathematically. But in languages like Java or C++, `left + right` can **overflow** if both are large integers. Using `left + (right - left) / 2` avoids that. In TypeScript/JavaScript, numbers are 64-bit floats, so overflow isn't really an issue. But using the safer version is a **good habit** — interviewers notice it, and it shows you understand the edge cases. ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(log n) | | Space | O(1) | --- ## The Three Templates: Mastering the Variations Here's where things get interesting. Not every binary search problem is "find the exact target." Sometimes you need the **first** occurrence, the **last** occurrence, or the **boundary** where a condition flips. There are three main templates, and knowing when to use each one is what separates someone who "knows binary search" from someone who can actually **solve problems** with it. --- ### Template 1: Basic Binary Search (Find Exact Match) This is what we just covered. The loop runs while `left <= right`, and you return `mid` when you find the target. ```typescript function basicBinarySearch(nums: number[], target: number): number { let left = 0; let right = nums.length - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) return mid; else if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } ``` **When to use it:** You need to find an exact value in a sorted array. Simple, clean, done. **Key detail:** The loop condition is `left <= right` (note the equals sign). When `left > right`, the search space is empty. --- ### Template 2: Find Left Boundary (First Position) What if the array has duplicates and you want the **first** occurrence? Or you want the **leftmost** position where a condition becomes true? The trick: when you find the target, **don't stop**. Instead, record it and keep searching left. ```typescript function findLeftBoundary(nums: number[], target: number): number { let left = 0; let right = nums.length - 1; let result = -1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) { result = mid; right = mid - 1; // keep searching left } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } ``` **Alternative form** (commonly seen in competitive programming): ```typescript function lowerBound(nums: number[], target: number): number { let left = 0; let right = nums.length; while (left < right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } ``` **When to use it:** Find the first position of a value, find the insertion point, or find where a monotonic condition first becomes true. **Key detail:** The loop condition is `left < right` (no equals). When the loop ends, `left === right` and that's your answer. --- ### Template 3: Find Right Boundary (Last Position) Same idea, but searching for the **last** occurrence. When you find the target, keep searching right. ```typescript function findRightBoundary(nums: number[], target: number): number { let left = 0; let right = nums.length - 1; let result = -1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) { result = mid; left = mid + 1; // keep searching right } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } ``` **Alternative form:** ```typescript function upperBound(nums: number[], target: number): number { let left = 0; let right = nums.length; while (left < right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] <= target) { left = mid + 1; } else { right = mid; } } return left - 1; } ``` **When to use it:** Find the last position of a value, or find where a monotonic condition last holds true. --- ### Template Comparison at a Glance | Template | Loop Condition | On Match | Returns | |----------|---------------|----------|---------| | Basic | `left <= right` | Return immediately | Exact index or -1 | | Left Boundary | `left < right` | Shrink right (`right = mid`) | First valid position | | Right Boundary | `left < right` | Shrink left (`left = mid + 1`) | Last valid position | > The difference between these templates is subtle — just one or two characters in the code. But those characters determine whether your solution works or falls into an infinite loop. This is why binary search has a reputation for off-by-one errors. --- ## LeetCode 34: Find First and Last Position of Element in Sorted Array This is the perfect problem to put Templates 2 and 3 to work. It's a classic, it's clean, and it forces you to understand boundaries. ### Problem > Given an array of integers `nums` sorted in non-decreasing order, find the starting and ending position of a given target value. If the target is not found, return `[-1, -1]`. You must write an algorithm with O(log n) runtime complexity. ### Example ``` Input: nums = [5, 7, 7, 8, 8, 10], target = 8 Output: [3, 4] Input: nums = [5, 7, 7, 8, 8, 10], target = 6 Output: [-1, -1] ``` ### The Insight Run binary search **twice** — once to find the leftmost 8, once to find the rightmost 8. ### TypeScript Solution ```typescript function searchRange(nums: number[], target: number): [number, number] { return [findFirst(nums, target), findLast(nums, target)]; } function findFirst(nums: number[], target: number): number { let left = 0; let right = nums.length - 1; let result = -1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) { result = mid; right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } function findLast(nums: number[], target: number): number { let left = 0; let right = nums.length - 1; let result = -1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) { result = mid; left = mid + 1; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } ``` ### Visual Step-Through Finding the **first** 8 in `[5, 7, 7, 8, 8, 10]`: ``` Step 1: left=0, right=5, mid=2 → nums[2]=7 < 8 → left=3 Step 2: left=3, right=5, mid=4 → nums[4]=8 === 8 → result=4, right=3 Step 3: left=3, right=3, mid=3 → nums[3]=8 === 8 → result=3, right=2 Step 4: left=3, right=2 → loop ends → return 3 ✅ ``` Finding the **last** 8: ``` Step 1: left=0, right=5, mid=2 → nums[2]=7 < 8 → left=3 Step 2: left=3, right=5, mid=4 → nums[4]=8 === 8 → result=4, left=5 Step 3: left=5, right=5, mid=5 → nums[5]=10 > 8 → right=4 Step 4: left=5, right=4 → loop ends → return 4 ✅ ``` Result: `[3, 4]` ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(log n) — two binary searches, each O(log n) | | Space | O(1) | --- ## LeetCode 33: Search in Rotated Sorted Array This is one of those problems that makes people go, "Wait... binary search works here?" And the answer is yes — with a twist. ### Problem > You are given an integer array `nums` sorted in ascending order (with distinct values), and the array is **rotated** at some pivot. Given a target, return its index, or -1 if not found. You must achieve O(log n) time. ### Example ``` Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 Output: 4 Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3 Output: -1 ``` ### Why It's Tricky The array isn't fully sorted anymore. It's sorted in two halves, with a "break point" somewhere. A normal binary search won't know which direction to go. ``` Original sorted: [0, 1, 2, 4, 5, 6, 7] Rotated: [4, 5, 6, 7, 0, 1, 2] ← sorted → ← sorted → ``` ### The Key Insight At every step, **at least one half is sorted**. If `nums[left] <= nums[mid]`, the left half is sorted. Otherwise, the right half is sorted. Once you know which half is sorted, you can check if the target falls within that sorted range: - If it does → search that half - If it doesn't → search the other half ### TypeScript Solution ```typescript function search(nums: number[], target: number): number { let left = 0; let right = nums.length - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) return mid; if (nums[left] <= nums[mid]) { // left half is sorted if (target >= nums[left] && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } else { // right half is sorted if (target > nums[mid] && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1; } ``` ### Walkthrough Searching for `0` in `[4, 5, 6, 7, 0, 1, 2]`: ``` Step 1: left=0, right=6, mid=3 → nums[3]=7 nums[0]=4 <= nums[3]=7 → left half [4,5,6,7] is sorted target 0 is NOT in [4, 7] → search right: left=4 Step 2: left=4, right=6, mid=5 → nums[5]=1 nums[4]=0 <= nums[5]=1 → left half [0,1] is sorted target 0 IS in [0, 1] → search left: right=4 Step 3: left=4, right=4, mid=4 → nums[4]=0 === 0 → found! ✅ ``` > Think of it like this: you're in a hallway that bends. You can't see the whole thing, but at any point, you can tell which direction is a straight shot and which direction has the bend. You always know enough to make a smart choice. ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(log n) | | Space | O(1) | --- ## LeetCode 162: Find Peak Element Here's where binary search gets really interesting. The array **isn't sorted at all**. So how can binary search apply? ### Problem > A peak element is an element that is strictly greater than its neighbors. Given an integer array `nums`, find a peak element and return its index. The array may contain multiple peaks — return the index of any one. You may assume `nums[-1] = nums[n] = -∞`. ### Example ``` Input: nums = [1, 2, 3, 1] Output: 2 (nums[2] = 3 is a peak) Input: nums = [1, 2, 1, 3, 5, 6, 4] Output: 5 (nums[5] = 6 is a peak, index 1 is also valid) ``` ### The Key Insight Think about standing on a hill. If the ground to your right is higher than where you're standing, there **must** be a peak somewhere to the right (because the array ends at -∞). Same logic applies to the left. So at every `mid`: - If `nums[mid] < nums[mid + 1]` → a peak exists to the right → move right - Otherwise → a peak exists at `mid` or to the left → move left This gives us a binary search even though the array isn't sorted! ### TypeScript Solution ```typescript function findPeakElement(nums: number[]): number { let left = 0; let right = nums.length - 1; while (left < right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] < nums[mid + 1]) { left = mid + 1; } else { right = mid; } } return left; } ``` ### Walkthrough For `nums = [1, 2, 1, 3, 5, 6, 4]`: ``` Step 1: left=0, right=6, mid=3 → nums[3]=3 < nums[4]=5 → left=4 Step 2: left=4, right=6, mid=5 → nums[5]=6 > nums[6]=4 → right=5 Step 3: left=4, right=5, mid=4 → nums[4]=5 < nums[5]=6 → left=5 Step 4: left=5, right=5 → loop ends → return 5 ✅ (nums[5]=6 is a peak) ``` ### Why This Works We're not searching for a specific value — we're searching for a **structural property** (being greater than both neighbors). The fact that the array "ends" at -∞ on both sides guarantees at least one peak exists, and at every step we can eliminate half the search space. > This is a pivotal insight: binary search doesn't require a sorted array. It requires a way to **eliminate half the search space** at each step. ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(log n) | | Space | O(1) | --- ## LeetCode 74: Search a 2D Matrix Can you binary search a matrix? Absolutely — if the rows are sorted and each row starts where the previous one ended, the entire matrix is effectively a sorted 1D array. ### Problem > You are given an `m x n` matrix with the following properties: each row is sorted in ascending order, and the first integer of each row is greater than the last integer of the previous row. Given a target, return `true` if the target is in the matrix. ### Example ``` Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true ``` ### The Key Insight Flatten the 2D matrix into a 1D sorted array — conceptually, not literally. A matrix with `m` rows and `n` columns has `m * n` total elements. You can map any 1D index back to 2D coordinates: - **Row** = `Math.floor(index / n)` - **Column** = `index % n` ### TypeScript Solution ```typescript function searchMatrix(matrix: number[][], target: number): boolean { const m = matrix.length; const n = matrix[0].length; let left = 0; let right = m * n - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); const row = Math.floor(mid / n); const col = mid % n; const value = matrix[row][col]; if (value === target) return true; else if (value < target) left = mid + 1; else right = mid - 1; } return false; } ``` ### Walkthrough For `matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]`, `target = 3`: ``` m=3, n=4 → total elements = 12 Conceptual 1D array: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60] Step 1: left=0, right=11, mid=5 → row=1, col=1 → value=11 > 3 → right=4 Step 2: left=0, right=4, mid=2 → row=0, col=2 → value=5 > 3 → right=1 Step 3: left=0, right=1, mid=0 → row=0, col=0 → value=1 < 3 → left=1 Step 4: left=1, right=1, mid=1 → row=0, col=1 → value=3 === 3 → true ✅ ``` > The matrix never actually gets flattened. We just use math to pretend it is. That's the elegance — zero extra space, full binary search power. ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(log(m × n)) | | Space | O(1) | --- ## LeetCode 69: Sqrt(x) — Binary Search on Answer Space This problem introduces a critical concept: **binary search doesn't have to search an array**. It can search a range of possible answers. ### Problem > Given a non-negative integer `x`, compute and return the square root of `x`. Since the return type is an integer, the decimal part is truncated. You may not use any built-in exponent function or operator. ### Example ``` Input: x = 8 Output: 2 (√8 = 2.828..., truncated to 2) ``` ### The Key Insight The answer is some integer between `0` and `x`. We're searching for the **largest number whose square is ≤ x**. That's a search space — and it's sorted! (1² < 2² < 3² < ...). This is **binary search on the answer space**: instead of searching an array, you search a range of candidate answers. ### TypeScript Solution ```typescript function mySqrt(x: number): number { if (x < 2) return x; let left = 1; let right = Math.floor(x / 2); let result = 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (mid * mid === x) { return mid; } else if (mid * mid < x) { result = mid; left = mid + 1; } else { right = mid - 1; } } return result; } ``` ### Walkthrough For `x = 8`: ``` left=1, right=4 Step 1: mid=2 → 2*2=4 < 8 → result=2, left=3 Step 2: mid=3 → 3*3=9 > 8 → right=2 Step 3: left=3, right=2 → loop ends → return 2 ✅ ``` ### Why This Matters This is the gateway to a whole class of binary search problems. Instead of "find this value in an array," you're solving "find the best answer in a range." This pattern shows up in problems about: - Minimizing a maximum value - Maximizing a minimum value - Finding thresholds - Optimization under constraints > Once you see that binary search can work on **any monotonic search space** — not just arrays — a whole new world of problems opens up. ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(log x) | | Space | O(1) | --- ## LeetCode 153: Find Minimum in Rotated Sorted Array Another rotated array problem, but this time we're not searching for a target — we're finding the minimum element. ### Problem > Given an array of length `n` sorted in ascending order that is **rotated** between 1 and n times, find the minimum element. All elements are unique. ### Example ``` Input: nums = [3, 4, 5, 1, 2] Output: 1 Input: nums = [4, 5, 6, 7, 0, 1, 2] Output: 0 ``` ### The Key Insight The minimum element is at the **rotation point** — the place where the sorted order breaks. We can find it by comparing `mid` with `right`: - If `nums[mid] > nums[right]` → the rotation point (and minimum) is to the right of `mid` - If `nums[mid] <= nums[right]` → `mid` could be the minimum, or it's to the left ### TypeScript Solution ```typescript function findMin(nums: number[]): number { let left = 0; let right = nums.length - 1; while (left < right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] > nums[right]) { left = mid + 1; } else { right = mid; } } return nums[left]; } ``` ### Walkthrough For `nums = [4, 5, 6, 7, 0, 1, 2]`: ``` Step 1: left=0, right=6, mid=3 → nums[3]=7 > nums[6]=2 → left=4 Step 2: left=4, right=6, mid=5 → nums[5]=1 < nums[6]=2 → right=5 Step 3: left=4, right=5, mid=4 → nums[4]=0 < nums[5]=1 → right=4 Step 4: left=4, right=4 → loop ends → nums[4]=0 ✅ ``` ### Why Compare with `right` Instead of `left`? Comparing with `left` breaks in certain cases. Consider `[2, 1]`: `mid=0`, `nums[0]=2 > nums[0]=2` is false, so we'd set `right=0` and return `nums[0]=2` — wrong! The minimum is 1. Comparing with `right` works because the minimum is always in the "unsorted" portion, and comparing with `right` correctly identifies which side the break is on. ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(log n) | | Space | O(1) | --- ## LeetCode 875: Koko Eating Bananas — Binary Search on Abstract Search Space This is where binary search gets really fun. No arrays. No sorted data. Just pure search space thinking. ### Problem > Koko loves eating bananas. There are `n` piles of bananas, and Koko can eat `k` bananas per hour. Each hour, she picks a pile and eats `k` bananas from it. If the pile has fewer than `k` bananas, she eats the whole pile and waits for the next hour. She has `h` hours to eat all the bananas. Find the **minimum** `k` such that she can eat all bananas within `h` hours. ### Example ``` Input: piles = [3, 6, 7, 11], h = 8 Output: 4 ``` ### Why Binary Search? Think about the eating speed `k`: - If `k` is very large (say, max pile size), Koko finishes easily — she eats each pile in one hour - If `k` is 1, she might need way more hours than allowed - As `k` increases, the total hours needed **monotonically decreases** That monotonic relationship is the key! We're searching for the **smallest `k`** where Koko finishes in time. This is a **left boundary** search on the answer space. ### TypeScript Solution ```typescript function minEatingSpeed(piles: number[], h: number): number { let left = 1; let right = Math.max(...piles); while (left < right) { const mid = left + Math.floor((right - left) / 2); if (canFinish(piles, mid, h)) { right = mid; } else { left = mid + 1; } } return left; } function canFinish(piles: number[], speed: number, h: number): boolean { let hours = 0; for (const pile of piles) { hours += Math.ceil(pile / speed); } return hours <= h; } ``` ### Walkthrough For `piles = [3, 6, 7, 11]`, `h = 8`: ``` Search space: k from 1 to 11 Step 1: left=1, right=11, mid=6 Hours at speed 6: ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 = 6 6 <= 8 → can finish → right=6 Step 2: left=1, right=6, mid=3 Hours at speed 3: ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3) = 1+2+3+4 = 10 10 > 8 → can't finish → left=4 Step 3: left=4, right=6, mid=5 Hours at speed 5: ceil(3/5)+ceil(6/5)+ceil(7/5)+ceil(11/5) = 1+2+2+3 = 8 8 <= 8 → can finish → right=5 Step 4: left=4, right=5, mid=4 Hours at speed 4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 8 <= 8 → can finish → right=4 Step 5: left=4, right=4 → loop ends → return 4 ✅ ``` ### The Pattern: "Minimize the Maximum" / "Maximize the Minimum" Koko Eating Bananas is an example of a broader pattern: 1. Define a **search space** of possible answers 2. Write a **feasibility function** that checks whether a given answer works 3. Binary search for the **optimal** answer (smallest valid or largest valid) This pattern appears in tons of problems: - Minimize the maximum distance between gas stations - Maximize the minimum sweetness when splitting chocolate - Find the minimum capacity to ship packages within D days - Split array into groups with minimum largest sum > Whenever a problem asks you to minimize a maximum or maximize a minimum, and the feasibility check is monotonic, binary search on the answer space is your move. ### Complexity | Metric | Complexity | |--------|-----------| | Time | O(n × log(max(piles))) | | Space | O(1) | Where `n` is the number of piles. We do O(log(max)) binary search steps, and each feasibility check is O(n). --- ## Binary Search on Abstract Conditions: The Generalized Pattern Everything we've covered so far points to a single, powerful idea. Let me spell it out clearly because this is the insight that will make binary search click for advanced problems. ### The Core Principle > Binary search applies whenever you have a **monotonic condition** over a search space. What does that mean? Imagine a sequence of answers: 1, 2, 3, 4, 5, 6, ... For each answer, some condition is either `false` or `true`. If the pattern looks like this: ``` Answer: 1 2 3 4 5 6 7 8 Feasible: false false false true true true true true ``` There's a clear **boundary** — everything before it is false, everything after is true (or vice versa). Binary search finds that boundary in O(log n) time. ### The Generalized Template ```typescript function binarySearchOnCondition(lo: number, hi: number): number { while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); if (condition(mid)) { hi = mid; // mid might be the answer, search left } else { lo = mid + 1; // mid is not valid, search right } } return lo; // lo === hi === the boundary point } ``` This works for: - Finding the **first** value where `condition` is true (left boundary) - Finding the **last** value where `condition` is false (right boundary — just flip the logic) - Any problem where you can define a monotonic predicate ### Examples in the Wild | Problem | Search Space | Condition | |---------|-------------|-----------| | Sqrt(x) | 1 to x | `mid * mid <= x` | | Koko Eating Bananas | 1 to max pile | `canFinish(speed)` | | Ship Packages in D Days | max weight to sum of weights | `canShip(capacity)` | | Split Array Largest Sum | max element to total sum | `canSplit(maxSum)` | | Magnetic Force (max min distance) | 1 to max position | `canPlace(distance)` | The specifics change, but the structure is identical every time. --- ## Putting It All Together: A Mental Framework Before we get to pitfalls, let's zoom out and see the big picture. Every binary search problem we've covered follows the same mental framework: **Step 1: Define the search space.** What are you searching over? It could be array indices, possible answer values, speeds, capacities, distances — anything. **Step 2: Define the condition.** What makes a candidate "valid"? Is it an exact match? A feasibility check? A comparison with a neighbor? **Step 3: Determine the monotonic property.** As you move through the search space, does the condition flip from false to true (or true to false) exactly once? If yes, binary search works. **Step 4: Choose the right template.** Exact match? Template 1. First/left boundary? Template 2. Answer space optimization? Template 3. **Step 5: Handle the edges.** What are the initial bounds? What do you return when the loop ends? This is where most bugs hide. Let's see this framework applied: | Problem | Search Space | Condition | Monotonic? | Template | |---------|-------------|-----------|------------|----------| | Classic search | Array indices | `nums[mid] === target` | Sorted order | 1 | | First position | Array indices | `nums[mid] >= target` | Yes (sorted) | 2 | | Peak element | Array indices | `nums[mid] > nums[mid+1]` | Local guarantee | 2 | | Sqrt(x) | 1 to x | `mid² <= x` | Yes | 3 | | Koko Bananas | 1 to max pile | `canFinish(speed)` | Yes | 3 | | Min in rotated | Array indices | `nums[mid] <= nums[right]` | Rotation structure | 2 | Once you internalize this framework, new binary search problems stop feeling new. They're just variations of the same five steps. --- ## Common Pitfalls: The Bugs That Get Everyone Binary search is conceptually simple but notoriously tricky to implement correctly. Here are the bugs that catch even experienced developers. --- ### Pitfall 1: Off-by-One Errors This is the #1 source of bugs. The difference between `left <= right` and `left < right`, between `right = mid` and `right = mid - 1` — these tiny changes determine whether your code works, returns the wrong answer, or loops forever. **The fix:** Pick a template and understand it deeply. Don't mix templates. If you're using Template 2 (`left < right`), then `right = mid`. If you're using Template 1 (`left <= right`), then `right = mid - 1`. ```typescript // Template 1: left <= right → update with mid ± 1 while (left <= right) { // right = mid - 1 or left = mid + 1 } // Template 2: left < right → right = mid (not mid - 1) while (left < right) { // right = mid or left = mid + 1 } ``` --- ### Pitfall 2: Infinite Loops This happens when pointers never converge. The classic case: ```typescript // DANGER: This can loop forever! while (left < right) { const mid = left + Math.floor((right - left) / 2); if (someCondition) { left = mid; // when left + 1 === right, mid === left, so left never changes! } else { right = mid; } } ``` **The fix:** If you ever set `left = mid` (without the +1), use `Math.ceil` instead of `Math.floor` for the mid calculation, or restructure your logic to use `left = mid + 1`. ```typescript // Safe: use ceil when setting left = mid const mid = left + Math.ceil((right - left) / 2); ``` --- ### Pitfall 3: Integer Overflow in Mid Calculation ```typescript // In languages with fixed-size integers (Java, C++): const mid = (left + right) / 2; // can overflow if left + right > MAX_INT // Safe version: const mid = left + Math.floor((right - left) / 2); // always safe ``` In TypeScript/JavaScript this isn't a practical issue, but it's a universal best practice and interviewers expect it. --- ### Pitfall 4: Forgetting the Preconditions Binary search only works when you can **eliminate half the search space** at each step. That requires: - A **sorted array**, OR - A **monotonic property** over the search space If neither is true, binary search doesn't apply. Don't force it. --- ### Pitfall 5: Wrong Initial Bounds Setting `right = nums.length` vs `right = nums.length - 1` matters! It depends on whether your search space is `[left, right]` (inclusive) or `[left, right)` (exclusive on the right). | Bounds Style | Initial `right` | Loop Condition | Mid Update | |-------------|-----------------|----------------|------------| | Inclusive `[l, r]` | `nums.length - 1` | `left <= right` | `right = mid - 1` | | Left-inclusive `[l, r)` | `nums.length` | `left < right` | `right = mid` | Pick one and stick with it. --- ## Pattern Recognition: When to Think Binary Search You're reading a problem. How do you know binary search is the move? Look for these signals: ### Signal 1: The Input is Sorted This is the most obvious clue. Sorted array + search = binary search. Every time. ### Signal 2: "Find the Minimum/Maximum That Satisfies..." "Find the minimum speed," "find the maximum distance," "what's the smallest capacity" — these scream binary search on the answer space. ### Signal 3: The Problem Requires O(log n) If the problem explicitly says O(log n) time, binary search is almost certainly involved. There aren't many other algorithms that achieve logarithmic time. ### Signal 4: You Can Define a Monotonic Condition Ask yourself: "If I increase/decrease the answer, does the feasibility only go in one direction?" If yes, binary search applies. ### Signal 5: The Search Space Can Be Halved Can you look at the middle and definitively rule out one half? That's the essential requirement. ### Signal 6: You See a Rotated or Modified Sorted Array Rotated sorted arrays are a classic binary search playground. The sorted property is broken globally but preserved locally. ### Quick Decision Flowchart ``` Is the input sorted (or has a monotonic property)? ├── Yes → Can you eliminate half the space at each step? │ ├── Yes → Binary Search! Choose the right template. │ └── No → Consider other approaches. └── No → Can you define a search space with a monotonic condition? ├── Yes → Binary Search on answer space! └── No → Binary search probably doesn't apply. ``` --- ## Cheat Sheet: Binary Search at a Glance ### Templates Quick Reference **Template 1 — Find Exact Match:** ```typescript let left = 0, right = n - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) return mid; else if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return -1; ``` **Template 2 — Find Left Boundary:** ```typescript let left = 0, right = n; while (left < right) { const mid = left + Math.floor((right - left) / 2); if (nums[mid] < target) left = mid + 1; else right = mid; } return left; ``` **Template 3 — Binary Search on Answer Space:** ```typescript let lo = minAnswer, hi = maxAnswer; while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); if (feasible(mid)) hi = mid; else lo = mid + 1; } return lo; ``` ### Problem → Template Mapping | Problem | Template | Key Insight | |---------|----------|------------| | Find target in sorted array | Template 1 | Direct comparison | | First/last position | Template 2 (modified) | Don't stop on match | | Search in rotated array | Template 1 | Determine sorted half | | Find peak element | Template 2 | Compare with neighbor | | Search 2D matrix | Template 1 | Index mapping | | Sqrt(x) | Template 3 | Answer space | | Min in rotated array | Template 2 | Compare mid with right | | Koko Eating Bananas | Template 3 | Feasibility function | ### Big O Reference | Operation | Time | Space | |-----------|------|-------| | Classic binary search | O(log n) | O(1) | | Binary search on answer space | O(n × log S) | O(1) | | Two binary searches (first/last) | O(log n) | O(1) | | Binary search on 2D matrix | O(log(m × n)) | O(1) | Where `S` is the size of the answer space and the feasibility check is O(n). --- ## What's Next? Binary search is one of those patterns that keeps showing up in unexpected places once you train your eye. You've now got the tools to handle it — from the classic sorted-array search all the way to abstract answer-space optimization. If you've been following the "Made Simple" series, here's how binary search connects to what you already know: - **Two Pointers** gave you the idea of narrowing a range with two indices — binary search takes that further with logarithmic elimination - **Sliding Window** taught you to think about search spaces and conditions — binary search on answer space uses similar "is this feasible?" thinking - **Hashmaps and Sets** are often the alternative to binary search when the data isn't sorted — knowing both helps you pick the right tool Coming up next in the series: - **Depth-First Search & Backtracking, Made Simple** — explore trees, graphs, and recursive state spaces - **Dynamic Programming, Made Simple** — the pattern that ties everything together --- ## Practice Roadmap If you want to build real fluency with binary search, here's a suggested order. Start easy and build up. ### Tier 1: Get the Basics Down | Problem | LeetCode # | Focus | |---------|-----------|-------| | Binary Search | 704 | Classic Template 1 | | Search Insert Position | 35 | Insertion point / lower bound | | Sqrt(x) | 69 | Answer space introduction | ### Tier 2: Apply the Templates | Problem | LeetCode # | Focus | |---------|-----------|-------| | First and Last Position | 34 | Left and right boundaries | | Find Peak Element | 162 | Binary search on unsorted data | | Search a 2D Matrix | 74 | Index mapping | ### Tier 3: Rotated Array Mastery | Problem | LeetCode # | Focus | |---------|-----------|-------| | Search in Rotated Sorted Array | 33 | Determine sorted half | | Find Minimum in Rotated Sorted Array | 153 | Compare with right boundary | | Search in Rotated Sorted Array II | 81 | Handle duplicates | ### Tier 4: Answer Space Problems | Problem | LeetCode # | Focus | |---------|-----------|-------| | Koko Eating Bananas | 875 | Feasibility function | | Capacity to Ship Packages | 1011 | Minimize maximum | | Split Array Largest Sum | 410 | Boundary of feasibility | | Magnetic Force Between Two Balls | 1552 | Maximize minimum | > Don't rush through these. For each problem, try to identify the five-step framework (search space, condition, monotonicity, template, edges) before you write any code. That's the real skill. --- ## Thanks for Reading If this guide helped binary search click for you, share it with someone who's studying. The best way to solidify understanding is to explain it to someone else. Go solve a few problems. Start with the classic search, work up to rotated arrays, and when you're ready, tackle a Koko Eating Bananas–style problem. You'll be surprised how natural it feels. Keep learning. Keep coding. You've got this. **Your Dev Brain, Now Thinking Logarithmically** ---

Problem Solving Patterns: Binary Search, Made Simple