46:"/_next/static/chunks/33yus346z0l_n.js" 47:"/_next/static/chunks/1r8ezocsukqp8.js" 48:"/_next/static/chunks/0iv56yrji_20j.js" 49:"/_next/static/chunks/0wa9m1-tphf9u.js" 4a:"/_next/static/chunks/08cuqqn_f60pp.js" 4b:"/_next/static/chunks/3zdsl3f9b0--r.js" 4c:"/_next/static/chunks/2j22cxchii_xx.js" 4d:"/_next/static/chunks/3bgoyiso1rhn7.js" 4e:"/_next/static/chunks/01a-3hvnqu8wl.js" 4f:"/_next/static/chunks/3m1xjj5kw5fie.js" 50:"/_next/static/chunks/0om3fkgfnicab.js" 51:"/_next/static/chunks/0gafyzg9j9yqj.js" 52:"/_next/static/chunks/20w4eaqlekefm.js" 53:"/_next/static/chunks/449--h5z1s6nq.js" 54:"/_next/static/chunks/3k2gyg36fnag_.js" 55:"/_next/static/chunks/18ggtgz2yf759.js" 56:"/_next/static/chunks/0hlb44ca7-4a2.js" 57:"/_next/static/chunks/253gnmj0-cj17.js" 58:"/_next/static/chunks/09nq57stwzkgf.js" 59:"/_next/static/chunks/082jo-0ajazgr.js" 5a:"/_next/static/chunks/2ozcrjb_hh74t.js" 5b:"/_next/static/chunks/05i8en-x14ibi.js" 5c:"/_next/static/chunks/32izpn90gvm22.js" 5d:"/_next/static/chunks/0jbzid2v9xv3h.js" 5e:"/_next/static/chunks/0i3-eynrkvqi7.js" 5f:"/_next/static/chunks/1tn-0fivsxsv1.js" 60:"/_next/static/chunks/34h36hyf_ggow.js" 61:"/_next/static/chunks/20329i6m_04t6.js" 62:"/_next/static/chunks/161uxd62cjny2.js" 63:"/_next/static/chunks/2k8pepwc4pxns.js" 64:I[593304,["$2b","$2c","$2d","$2e","$2f","$30","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61","$62","$63"],"OwnedHydration"] 65:T4d9,def can_ship_in_d_days(weights: list[int], D: int, capacity: int) -> bool: """ Feasibility predicate for shipping problem. Question: Can we ship all packages in D days with given capacity? Strategy: Greedily load each day until capacity is reached. Count days needed; return True if days_needed <= D. Time Complexity: O(n) where n = len(weights) """ days_needed = 1 # Start with day 1 current_load = 0 # Current day's load for weight in weights: # If this package fits in current day's ship if current_load + weight <= capacity: current_load += weight else: # Start a new day days_needed += 1 current_load = weight # Early termination: already exceeds D if days_needed > D: return False return days_needed <= D # Example usage weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] D = 5 print(can_ship_in_d_days(weights, D, 10)) # False (needs 10 days) print(can_ship_in_d_days(weights, D, 15)) # True (needs exactly 5 days) print(can_ship_in_d_days(weights, D, 20)) # True (needs 4 days) print(can_ship_in_d_days(weights, D, 55)) # True (needs 1 day)66:T815,def binary_search_on_answer(lo: int, hi: int, is_feasible) -> int: """ Generic template for binary search on answer space. This finds the MINIMUM feasible value (for minimization problems). Args: lo: Lower bound of answer space hi: Upper bound of answer space is_feasible: Predicate function (answer) -> bool Returns: The minimum value x such that is_feasible(x) == True Invariant: - All values < answer are infeasible - All values >= answer are feasible Time Complexity: O(log(hi - lo) * cost_of_is_feasible) """ answer = hi # Default to upper bound (always feasible) while lo <= hi: mid = lo + (hi - lo) // 2 if is_feasible(mid): # mid works! But maybe something smaller also works answer = mid # Record this as best so far hi = mid - 1 # Search for smaller feasible value else: # mid doesn't work; need larger value lo = mid + 1 return answer def ship_within_days(weights: list[int], D: int) -> int: """ Complete solution: Find minimum ship capacity to ship packages in D days. LeetCode 1011: Capacity To Ship Packages Within D Days """ # Step 1: Define search bounds lo = max(weights) # Must fit largest package hi = sum(weights) # Could ship all at once # Step 2: Define feasibility predicate def can_ship(capacity: int) -> bool: days_needed = 1 current_load = 0 for weight in weights: if current_load + weight <= capacity: current_load += weight else: days_needed += 1 current_load = weight return days_needed <= D # Step 3: Binary search for minimum feasible capacity return binary_search_on_answer(lo, hi, can_ship) # Example usage weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] D = 5 print(f"Minimum capacity: {ship_within_days(weights, D)}") # Output: 1545:["$","$L64",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792315921343,"state":{"data":{"json":{"id":"seed_7cf49b6d803a7229aaefb2f12dd29269","slug":"binary-search-on-answer-space","category":"Data Structures & Algorithms","topic":"Binary Search on Answer Space","title":"Binary Search on Answer Space","description":"Master the art of applying binary search to optimization problems where you search for feasible answer values rather than array elements. Learn to identify monotonic properties, formulate decision problems, and solve classic optimization challenges like capacity scheduling and array splitting.","difficulty":"ADVANCED","estimatedMinutes":90,"pages":[{"id":"seed_aed76c65cb1d5b4e52c60b6f97dd7fb9","title":"When the Search Target Is an Answer, Not an Element","order":0,"content":[{"id":"opening-hook","title":"Beyond Array Lookups: A New Dimension of Binary Search","content":[{"data":{"content":"You've mastered binary search for finding elements in a sorted array. Given `[1, 3, 5, 7, 9]` and target `5`, you can locate it in O(log n) time. But what happens when there's **no array to search**—when the 'answer' isn't stored anywhere, but rather needs to be discovered?\n\nConsider this problem:\n\n> *You have a conveyor belt carrying packages to be shipped within D days. Each package has a weight, and packages must be shipped in order. What is the **minimum ship capacity** needed to ship all packages within D days?*\n\nThere's no array containing 'ship capacities to check.' The answer is a **value** that must satisfy certain constraints. Yet binary search applies here with devastating efficiency. This page introduces this paradigm shift—from searching **elements** to searching **answer values**."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand: (1) the conceptual leap from element-search to answer-search, (2) how continuous or discrete solution spaces become searchable, (3) why this technique is called 'binary search on answer' and not optimization, and (4) the mental framework for recognizing these problems instantly.","variant":"info"},"type":"callout"}]},{"id":"traditional-binary-search","title":"The Traditional Binary Search Mental Model","content":[{"data":{"content":"Before we extend binary search, let's crystallize what traditional binary search actually does. Understanding its **essence** reveals why the extension is natural.\n\n**Traditional binary search has three components:**\n\n1. **Search Space**: A sorted array containing potential answers\n2. **Target**: A specific value you're looking for\n3. **Comparison Logic**: Determines whether to go left or right\n\nWhen you search for value `x` in array `[1, 3, 5, 7, 9]`, you're asking: *'Where does x appear?'* The array is **explicit**—every candidate is laid out before you."},"type":"text"},{"data":{"code":"def binary_search(arr: list[int], target: int) -> int:\n \"\"\"\n Traditional binary search: find target in sorted array.\n Returns index if found, -1 otherwise.\n \n Search Space: arr[left..right]\n Target: specific value to find\n Logic: compare arr[mid] to target\n \"\"\"\n left, right = 0, len(arr) - 1\n \n while left <= right:\n mid = left + (right - left) // 2\n \n if arr[mid] == target:\n return mid # Found it!\n elif arr[mid] < target:\n left = mid + 1 # Target is to the right\n else:\n right = mid - 1 # Target is to the left\n \n return -1 # Not found\n\n# Example usage\narr = [1, 3, 5, 7, 9]\nprint(binary_search(arr, 5)) # Output: 2 (index of 5)\nprint(binary_search(arr, 6)) # Output: -1 (not in array)","fileName":"traditional_binary_search.py","showLineNumbers":true},"type":"code"},{"data":{"content":"**The key insight**: Binary search works because the array is **sorted**, meaning there's a **monotonic relationship**. All elements to the left of `x` are smaller; all elements to the right are larger. This ordering allows us to eliminate half the search space with each comparison.\n\nBut here's the critical observation: **the sortedness of an array is just one instance of a broader principle.** Binary search works on *any* search space where a **monotonic property** allows us to eliminate half the candidates at each step."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Core Principle","content":"Binary search doesn't require an array. It requires a **range** with a **monotonic property**: a condition that changes from false to true (or true to false) exactly once as you move through the range. This is the secret that unlocks binary search on answer space.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"paradigm-shift","title":"The Paradigm Shift: From Elements to Answers","content":[{"data":{"content":"Now, let's make the conceptual leap. Instead of searching an array for an **element**, we search a **range of values** for an **optimal answer**.\n\n**The new mental model:**"},"type":"text"},{"data":{"rows":[["Search space: array elements","Search space: range of possible answers"],["Searching for: where target appears","Searching for: optimal feasible value"],["Comparison: `arr[mid] vs target`","Comparison: `canAchieve(mid)` (feasibility check)"],["Output: index of target","Output: the answer value itself"]],"headers":["Traditional Binary Search","Binary Search on Answer Space"]},"type":"table"},{"data":{"content":"The profound insight is that **the answer space itself becomes the 'array'**. If possible answers range from 1 to 1,000,000, we binary search this range—not by comparing array values, but by checking whether each candidate answer is **feasible**."},"type":"text"},{"data":{"left":[{"data":{"items":["Array: [1, 3, 5, 7, 9]","Target: 5","Question: 'Is arr[mid] equal to 5?'","Answer: The index where 5 lives","Search space: explicitly stored"],"title":{"icon":"BookOpen","text":"Traditional: Search for Element","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Range: [1, 1000000]","Target: minimum feasible capacity","Question: 'Can we ship with capacity mid?'","Answer: The capacity value itself","Search space: implicitly defined"],"title":{"icon":"Target","text":"New: Search for Answer","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**The feasibility function replaces the comparison.** In traditional search, we compare `arr[mid]` to the target. In answer-space search, we ask: *'Is this candidate answer achievable?'* or *'Does this value satisfy all constraints?'*\n\nThis is why the technique is sometimes called **'binary search the answer'** or **'binary search on solution space'**. We're not searching for where something is stored—we're searching for a value that optimizes an objective while satisfying constraints."},"type":"text"},{"data":{"icon":"Info","title":"Why 'Binary Search on Answer Space'?","content":"The name emphasizes that you're searching a space of *possible answers* (like ship capacities, maximum distances, or time limits), not a data structure. The 'answer' is what you output—the optimal value that solves the problem.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"implicit-search-space","title":"The Implicit Search Space","content":[{"data":{"content":"In traditional binary search, the search space is **explicit**: an array physically exists in memory. In answer-space binary search, the search space is **implicit**: it's a conceptual range of values, not a stored data structure.\n\n**Defining the implicit search space:**\n\nFor any answer-space problem, you must determine:\n\n1. **Lower Bound (lo)**: The smallest possible answer\n2. **Upper Bound (hi)**: The largest possible answer\n\nThese bounds come from problem constraints and logical reasoning. The 'array' you're searching is conceptually `[lo, lo+1, lo+2, ..., hi]` (for integers) or a continuous interval `[lo, hi]` (for real numbers)."},"type":"text"},{"data":{"input":"weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], D = 5","title":"Ship Packages Problem — Defining Bounds","output":"Minimum capacity = 15","description":"Given packages with weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and D = 5 days, find minimum ship capacity.","explanation":"Lower bound: max(weights) = 10. (Ship must hold at least the heaviest package.)\nUpper bound: sum(weights) = 55. (Worst case: ship everything in 1 day.)\n\nSearch space: [10, 55] — 46 candidates instead of checking all possibilities.\n\nWith binary search: log₂(46) ≈ 6 checks instead of 46 linear checks."},"type":"example"},{"data":{"content":"**Why bounds matter tremendously:**\n\nChoosing tight bounds is crucial for efficiency and correctness:\n\n- **Too tight lower bound**: You might miss the correct answer\n- **Too loose upper bound**: You waste search iterations\n- **Just right**: Minimal iterations, guaranteed correctness\n\nFor the shipping problem:\n- Lower bound `max(weights)` is necessary because the ship must fit the heaviest single package\n- Upper bound `sum(weights)` is sufficient because we could always ship everything in one day\n\nThis gives us a finite, bounded search space that binary search can efficiently explore."},"type":"text"},{"data":{"code":"def find_search_bounds_shipping(weights: list[int]) -> tuple[int, int]:\n \"\"\"\n Determine the implicit search space for shipping problem.\n \n Lower bound: Must fit the heaviest package\n Upper bound: Ship everything at once (worst case)\n \"\"\"\n lower_bound = max(weights) # Can't be smaller than largest package\n upper_bound = sum(weights) # Could ship all in 1 day\n \n return lower_bound, upper_bound\n\n# Example\nweights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\nlo, hi = find_search_bounds_shipping(weights)\nprint(f\"Search space: [{lo}, {hi}]\") # [10, 55]\nprint(f\"Search space size: {hi - lo + 1}\") # 46 candidates\nprint(f\"Binary search checks: ~{(hi - lo + 1).bit_length()}\") # ~6 checks","fileName":"defining_search_bounds.py","showLineNumbers":true},"type":"code"},{"data":{"icon":"AlertCircle","title":"Bound Selection Is Problem-Specific","content":"There's no universal formula for bounds. Each problem requires careful analysis. For minimization problems, the lower bound is the smallest theoretically possible value; for maximization, the upper bound is the largest. Incorrect bounds lead to wrong answers or missed optima.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"feasibility-predicate","title":"The Feasibility Predicate: The Heart of the Algorithm","content":[{"data":{"content":"The **feasibility predicate** is the function that replaces array comparison. Given a candidate answer `mid`, it returns:\n\n- **True**: This answer works (satisfies all constraints)\n- **False**: This answer doesn't work (violates at least one constraint)\n\nThis function is the **most important piece** of any answer-space binary search solution. Its correctness determines algorithm correctness; its efficiency determines overall time complexity.\n\n**Designing the feasibility predicate:**\n\nThe predicate must answer a yes/no question: *'Can we achieve the goal with answer = mid?'* For the shipping problem: *'Can we ship all packages in D days with capacity = mid?'*"},"type":"text"},{"data":{"code":"$65","fileName":"feasibility_predicate.py","showLineNumbers":true},"type":"code"},{"data":{"content":"**Critical properties of the feasibility predicate:**\n\n1. **Deterministic**: Same input always gives same output\n2. **Efficient**: Usually O(n) or O(n log n); otherwise binary search gains are lost\n3. **Monotonic with respect to the search space**: This is essential for binary search to work\n\nThe **monotonic property** means:\n- If `canAchieve(x)` is True, then `canAchieve(x+1)` is also True (for minimization)\n- If `canAchieve(x)` is False, then `canAchieve(x-1)` is also False (for minimization)\n\nThis creates a clean boundary in the search space: all values below some threshold are infeasible; all values at or above are feasible."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Predicate Design Principle","content":"Always make the predicate answer a **simple yes/no question** about feasibility. Complex predicates with multiple return values or special cases introduce bugs. If you find yourself returning -1, 0, or 1, you're likely overcomplicating the design.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"search-space-partition","title":"Visualizing the Search Space Partition","content":[{"data":{"content":"Binary search on answer space works because the feasibility predicate **partitions** the search space into two contiguous regions:\n\n```\n[lo .................... X .................... hi]\n |←— INFEASIBLE —→|←——— FEASIBLE ———→|\n```\n\nFor **minimization** problems (finding smallest feasible answer):\n- All values less than the optimal answer X are infeasible\n- All values ≥ X are feasible\n- We want to find X, the **first** feasible value\n\nFor **maximization** problems (finding largest feasible answer):\n- All values ≤ X are feasible \n- All values greater than X are infeasible\n- We want to find X, the **last** feasible value"},"type":"text"},{"data":{"rows":[["10","10 days","❌ False","INFEASIBLE"],["11","9 days","❌ False","INFEASIBLE"],["12","8 days","❌ False","INFEASIBLE"],["13","6 days","❌ False","INFEASIBLE"],["14","6 days","❌ False","INFEASIBLE"],["**15**","**5 days**","**✓ True**","**BOUNDARY (Answer)**"],["16","5 days","✓ True","FEASIBLE"],["20","4 days","✓ True","FEASIBLE"],["30","3 days","✓ True","FEASIBLE"],["55","1 day","✓ True","FEASIBLE"]],"caption":"Shipping Problem: Feasibility Across Answer Space","headers":["Capacity","Days Needed","Feasible (D=5)?","Region"]},"type":"table"},{"data":{"content":"Notice the **clean partition**: every capacity below 15 is infeasible, and every capacity at or above 15 is feasible. The answer is 15—the boundary point where feasibility changes.\n\nBinary search finds this boundary efficiently by:\n1. Checking the midpoint `mid`\n2. If `mid` is feasible, the answer is at `mid` or to its left (for minimization)\n3. If `mid` is infeasible, the answer is to the right of `mid`\n4. Repeat until the boundary is found\n\nThis is exactly like finding the first True value in an array `[False, False, False, False, False, True, True, True, ...]`."},"type":"text"},{"data":{"icon":"Info","title":"The Partition Must Be Clean","content":"If the feasibility function doesn't create a clean partition (e.g., True, False, True, False randomly), binary search won't work. This is why verifying the monotonic property is essential before applying this technique.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"complete-algorithm","title":"The Complete Algorithm Template","content":[{"data":{"content":"Now let's assemble all the pieces into a complete algorithm. The template applies to virtually all 'binary search on answer' problems:\n\n**Algorithm structure:**\n1. **Define search bounds**: `lo` = minimum possible answer, `hi` = maximum possible answer\n2. **Define feasibility predicate**: `canAchieve(mid)` returns True/False\n3. **Binary search** to find the optimal boundary point\n4. **Return the answer**"},"type":"text"},{"data":{"code":"$66","fileName":"binary_search_on_answer_template.py","showLineNumbers":true},"type":"code"},{"data":{"content":"**Complexity analysis:**\n\n- **Binary search iterations**: O(log(hi - lo))\n- **Each iteration**: O(n) for the feasibility check\n- **Total time**: O(n × log(hi - lo))\n\nFor the shipping problem with weights summing to S:\n- Search space: O(S) values\n- Total time: O(n × log S)\n\nThis is dramatically better than brute force, which would try every capacity and take O(S × n) time."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Template Variations","content":"For maximization problems, swap the logic: when feasible, search right (lo = mid + 1); when infeasible, search left (hi = mid - 1). The answer becomes the last feasible value rather than the first.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"recognition-patterns","title":"Recognizing Answer-Space Binary Search Problems","content":[{"data":{"content":"The key skill is **recognizing** when a problem can be solved with binary search on answer—even when the problem statement doesn't mention search at all. Here are the telltale signs:"},"type":"text"},{"data":{"items":["**Optimization language**: 'Minimize the maximum X' or 'Maximize the minimum Y' — classic indicator of answer-space search","**Bounded answer range**: The answer must lie within a finite, known range that you can determine from constraints","**Feasibility can be checked**: Given a candidate answer, you can efficiently determine if it's achievable","**Monotonic feasibility**: If answer X works, then X+1 definitely works (or vice versa for max problems)","**Keywords**: 'minimum capacity', 'maximum distance', 'smallest time', 'largest possible', 'at most K', 'within D days'","**Constraint satisfaction**: The problem asks for a value that satisfies multiple constraints simultaneously"],"title":{"icon":"Target","text":"Recognition Patterns","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"content":"**The mental transformation:**\n\nOriginal problem:\n> *'What is the minimum X such that [conditions are satisfied]?'*\n\nTransformed to binary search:\n> *'For a given X, can [conditions be satisfied]? Binary search to find the smallest such X.'*\n\nThis transformation turns an **optimization problem** into a **decision problem**. Binary search then efficiently explores the decision space."},"type":"text"},{"data":{"left":[{"data":{"items":["Minimum ship capacity","Maximum minimum distance between points","Smallest largest sum when splitting array","Minimum time to complete all tasks","Maximum number of items with budget"],"title":{"icon":"CheckCircle","text":"Good Fit for Answer-Space Search","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Find all valid answers (not optimization)","Non-monotonic feasibility","Discrete choices without ordering","Answer depends on path, not just value","Feasibility check is exponential"],"title":{"icon":"XCircle","text":"NOT Suitable for This Technique","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"Lightbulb","title":"The Reframing Trick","content":"When you see an optimization problem, ask: 'If I knew the answer was X, could I verify it easily?' If yes, you likely have a binary search on answer problem. The verification becomes your feasibility predicate.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"common-mistakes","title":"Common Mistakes and Pitfalls","content":[{"data":{"content":"Binary search on answer space is powerful but error-prone. Here are the most common mistakes and how to avoid them:"},"type":"text"},{"data":{"type":"ordered","items":["**Wrong bounds**: Setting `lo` too high or `hi` too low causes missing the optimal answer. Always err on the side of wider bounds if unsure, then tighten based on problem analysis.","**Non-monotonic predicate**: If your feasibility function isn't monotonic (flips between True/False multiple times), binary search will fail silently. Always verify monotonicity before implementing.","**Incorrect boundary logic**: Confusing when to search left vs. right, or when to update the answer. Use the invariant: 'answer is the smallest (or largest) feasible value seen so far.'","**Off-by-one errors**: The classic binary search bug. Ensure your loop condition (`lo <= hi` vs `lo < hi`) matches your update logic (`mid + 1` vs `mid`).","**Inefficient feasibility check**: If the predicate is O(n²) and search space is O(S), total time is O(n² log S)—possibly worse than brute force! Keep predicates efficient.","**Integer overflow in bounds**: When searching large ranges (e.g., up to 10⁹), ensure `lo + hi` doesn't overflow. Use `mid = lo + (hi - lo) // 2` instead of `(lo + hi) // 2`."],"title":{"icon":"AlertCircle","text":"Pitfall Catalog","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"code":"# ❌ WRONG: Bounds too tight - might miss answer\ndef bad_bounds(weights, D):\n lo = min(weights) # Wrong! Must be >= max(weights)\n hi = sum(weights) // D # Wrong! Might need more capacity\n # ... this fails for many inputs\n\n# ❌ WRONG: Incorrect update logic\ndef bad_update_logic(lo, hi, is_feasible):\n while lo <= hi:\n mid = (lo + hi) // 2\n if is_feasible(mid):\n lo = mid # BUG: Never terminates! lo never moves up\n else:\n hi = mid - 1\n return lo\n\n# ✓ CORRECT: Proper minimization template\ndef correct_minimization(lo, hi, is_feasible):\n answer = hi\n while lo <= hi:\n mid = lo + (hi - lo) // 2\n if is_feasible(mid):\n answer = mid\n hi = mid - 1 # Try smaller\n else:\n lo = mid + 1 # Need larger\n return answer","fileName":"common_bug_examples.py","showLineNumbers":true},"type":"code"},{"data":{"icon":"AlertCircle","title":"Debug Strategy","content":"When your solution fails, first verify: (1) Are bounds definitely correct? Test at boundaries. (2) Does the predicate correctly say True/False? Test manually on examples. (3) Does feasibility have the monotonic property? Check a few consecutive values.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":8},{"id":"summary","title":"Summary: The Answer-Space Paradigm","content":[{"data":{"content":"We've covered a major conceptual expansion of binary search. Let's consolidate the key ideas:"},"type":"text"},{"data":{"type":"ordered","items":["**Binary search works on any monotonic search space** — not just arrays. The 'sortedness' of arrays is just one instance of monotonicity.","**Answer-space search has implicit search space** — ranges like [min_possible, max_possible] rather than stored elements.","**The feasibility predicate is the core** — a function that answers 'Is this candidate answer achievable?' The predicate must be efficient and monotonic.","**Feasibility partitions the search space** — into infeasible (below boundary) and feasible (at/above boundary). We find the boundary.","**Recognition comes from problem structure** — 'minimize maximum', 'find smallest X such that', bounded answers, and verifiable constraints all signal answer-space search.","**Complexity is O(log(range) × predicate_cost)** — often O(n log S) where S is the answer-space size."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's next:**\n\nNow that you understand the paradigm shift from element-search to answer-search, the next page explores **monotonic functions and decision problems** in depth. We'll formalize what makes a problem suitable for binary search on answer and develop the mathematical intuition that guarantees correctness."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the fundamental paradigm shift from searching for elements to searching for answers. This simple but profound insight unlocks a vast category of optimization problems that become tractable through binary search. Next, we'll deepen our understanding of why this technique works: the mathematics of monotonic functions and decision problems.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":9}],"isLocked":false},{"id":"seed_1504ac3e7cbc70dc2de82b39f2e42b87","title":"Monotonic Functions and Decision Problems","order":1,"content":null,"isLocked":true},{"id":"seed_26be73aa76eb6c203850bc65ee7fbfd1","title":"Minimizing the Maximum / Maximizing the Minimum","order":2,"content":null,"isLocked":true},{"id":"seed_849a8afc770e5788e7ea56afdae34dcd","title":"Classic Problems — Capacity to Ship, Split Array","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792315921330,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"binary-search-on-answer-space"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"binary-search-on-answer-space\"},\"type\":\"query\"}]"},{"dehydratedAt":1792315921344,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792315921339,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_7cf49b6d803a7229aaefb2f12dd29269"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_7cf49b6d803a7229aaefb2f12dd29269\"},\"type\":\"query\"}]"},{"dehydratedAt":1792315921344,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792315921340,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_1504ac3e7cbc70dc2de82b39f2e42b87"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_1504ac3e7cbc70dc2de82b39f2e42b87\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792315921344,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792315921340,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_1504ac3e7cbc70dc2de82b39f2e42b87"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_1504ac3e7cbc70dc2de82b39f2e42b87\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792315921344,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792315921340,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_1504ac3e7cbc70dc2de82b39f2e42b87"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_1504ac3e7cbc70dc2de82b39f2e42b87\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792315921344,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_1504ac3e7cbc70dc2de82b39f2e42b87","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_1504ac3e7cbc70dc2de82b39f2e42b87\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@67"}]},"children":"$L68"}]