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:T409,// Binary search works when there's a single transition point // Example: Finding first element >= target in sorted array function binarySearchForTransition( arr: T[], predicate: (element: T) => boolean ): number { // Predicate must satisfy: false...false,true...true // Returns index of first 'true', or arr.length if all false let left = 0; let right = arr.length; while (left < right) { const mid = left + Math.floor((right - left) / 2); if (predicate(arr[mid])) { right = mid; // First true might be here or earlier } else { left = mid + 1; // First true must be after mid } } return left; } // Usage: Find first element >= 15 in [1, 5, 10, 15, 20, 25] const arr = [1, 5, 10, 15, 20, 25]; const result = binarySearchForTransition(arr, x => x >= 15); // predicate results: [false, false, false, true, true, true] // ^ transition at index 3 console.log(result); // 366:T545,Understanding when binary search doesn't apply isn't just academic—these situations arise constantly in practice. Here are real-world optimization problems that demand ternary search (or similar techniques): **1. Machine Learning Hyperparameter Tuning** You're training a neural network and sweeping the learning rate from 0.0001 to 1.0. Too low and training is slow. Too high and training diverges. The validation accuracy as a function of learning rate is unimodal—there's a sweet spot, and performance drops on either side. **2. Economics — Optimal Pricing** The profit function for a product often looks like an inverted parabola: price too low means high volume but low margins; price too high means low volume. Somewhere in between is the revenue-maximizing price. **3. Physics — Projectile Range** The distance a projectile travels as a function of launch angle (with fixed velocity) is unimodal. At 0° or 90°, the projectile goes nowhere. Maximum range occurs at 45° (in a vacuum). You might need to find this optimal angle numerically. **4. Competitive Programming — Resource Allocation** Many problems involve allocating resources where too little or too much allocation is suboptimal. For instance, minimizing the time to complete tasks when adding workers helps initially but eventually causes coordination overhead.67:T40b,Let's build geometric intuition for why ternary search works where binary search fails. **Binary Search Geometry** In binary search, the search space is a line segment. Each comparison divides this segment in half. The answer lies somewhere on the segment, and each query tells you definitively which half contains it. ``` [====|====] After querying midpoint: [====] "Answer is in left half" [====] or "Answer is in right half" ``` **Ternary Search Geometry** In ternary search, we also have a line segment, but we divide it into thirds using two points. Each pair of queries tells us which third to eliminate: ``` [===|===|===] After querying two points: [===|===] "Eliminate right third" if f(m1) > f(m2) [===|===] "Eliminate left third" if f(m1) < f(m2) ``` The key difference: binary search gets definitive information from one query; ternary search needs two queries to get definitive information. But ternary search can handle problems where single-point queries are insufficient.68:T42f,**Why Thirds and Not Halves?** A natural question: if we need two query points, why not divide into halves with points at 1/3 and 2/3? Actually, there's flexibility here! The key constraint is: 1. We need two distinct points `m1 < m2` to compare 2. The points should be positioned so that each comparison eliminates a substantial portion 3. We want to minimize the number of function evaluations Positioning `m1` at 1/3 and `m2` at 2/3 gives us: - If eliminating left third: new interval is 2/3 the size - If eliminating right third: new interval is 2/3 the size This gives us a logarithmic convergence rate with base 3/2, which corresponds to O(log n) complexity but with a larger constant factor than binary search. **The Golden Section Alternative** Interestingly, there's an optimization called *golden section search* that places points using the golden ratio (≈ 0.618). This allows reusing one of the function evaluations in the next iteration, reducing the amortized cost from 2 evaluations per iteration to just over 1. We'll explore this in a later page.45:["$","$L64",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792318333936,"state":{"data":{"json":{"id":"seed_4789e379a0d1c65efe5ba1334a08e596","slug":"ternary-search","category":"Data Structures & Algorithms","topic":"Ternary Search","title":"Ternary Search — Finding Extrema in Unimodal Functions","description":"Master ternary search, a powerful algorithm for finding maximum or minimum values in unimodal functions. Understand when binary search fails and how ternary search fills the gap for optimization problems on continuous domains.","difficulty":"INTERMEDIATE","estimatedMinutes":55,"pages":[{"id":"seed_4938f82ef4bb7378c5784cf258839120","title":"When Binary Search Doesn't Apply","order":0,"content":[{"id":"opening-hook","title":"The Limits of a Powerful Tool","content":[{"data":{"content":"Binary search is one of the most elegant and powerful algorithms in computer science. It transforms O(n) linear searches into O(log n) operations by repeatedly halving the search space. You've likely used it countless times—finding elements in sorted arrays, locating insertion points, or searching for boundary conditions.\n\nBut here's a critical insight that many developers miss: **binary search has strict preconditions**. When those preconditions aren't met, binary search doesn't just perform poorly—it can produce completely incorrect results or fail to find valid answers altogether.\n\nUnderstanding when binary search *doesn't* apply is just as important as knowing how to implement it. This understanding opens the door to alternative algorithms designed for different problem structures, and ternary search is one of the most important among them."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the fundamental requirements for binary search, recognize problem types where those requirements are violated, and appreciate why these violations demand a fundamentally different algorithmic approach rather than ad-hoc modifications to binary search.","variant":"info"},"type":"callout"}]},{"id":"binary-search-prerequisites","title":"Binary Search Prerequisites — A Deep Dive","content":[{"data":{"content":"Before exploring what binary search *can't* do, let's crystallize what it *requires*. Binary search operates on a deceptively simple principle: given a structured search space, eliminate half of the remaining candidates with each comparison. But this simple principle demands rigorous structural properties.\n\n**The Monotonicity Requirement**\n\nBinary search requires **monotonicity** in some form. The classic application is a sorted array where elements monotonically increase (or decrease). But more generally, binary search works whenever you can formulate your problem as finding a boundary in a sequence of boolean predicates:\n\n- Let `P(x)` be a predicate that is `false` for all x < boundary and `true` for all x ≥ boundary\n- Or equivalently, `P(x)` transitions from `false` to `true` exactly once\n\nThis is the essence of binary search: **there must be a single transition point** in your search space."},"type":"text"},{"data":{"fileName":"BinarySearchPredicate.java","languages":[{"code":"$65","label":"TypeScript","value":"typescript"},{"code":"# Binary search works when there's a single transition point\n# Example: Finding first element >= target in sorted array\n\nfrom typing import Callable, List, TypeVar\n\nT = TypeVar('T')\n\ndef binary_search_for_transition(\n arr: List[T],\n predicate: Callable[[T], bool]\n) -> int:\n \"\"\"\n Predicate must satisfy: false...false,true...true\n Returns index of first 'true', or len(arr) if all false\n \"\"\"\n left = 0\n right = len(arr)\n \n while left < right:\n mid = left + (right - left) // 2\n \n if predicate(arr[mid]):\n right = mid # First true might be here or earlier\n else:\n left = mid + 1 # First true must be after mid\n \n return left\n\n# Usage: Find first element >= 15 in [1, 5, 10, 15, 20, 25]\narr = [1, 5, 10, 15, 20, 25]\nresult = binary_search_for_transition(arr, lambda x: x >= 15)\n# predicate results: [False, False, False, True, True, True]\n# ^ transition at index 3\nprint(result) # 3","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"**The Decision Property**\n\nAt each step of binary search, you must be able to make a *decisive* choice about which half of the search space to eliminate. This decision must be:\n\n1. **Correct** — Never eliminate the portion containing the answer\n2. **Substantive** — Always eliminate at least one element (or a constant fraction)\n3. **Deterministic** — Given the same state, always make the same choice\n\nIf you can look at a middle element and definitively say \"the answer is in the left half\" or \"the answer is in the right half,\" binary search applies. If you sometimes can't make this determination—or if you must explore *both* halves—binary search breaks down."},"type":"text"},{"data":{"rows":[["Monotonicity","P(x) = false for x < k, true for x ≥ k","Values transition exactly once across the search space"],["Decisiveness","Each comparison eliminates ≥ half of candidates","You never need to explore both directions"],["Single Answer Region","Answer exists in a contiguous region","There's one block of valid answers, not scattered islands"],["Comparable Elements","Elements support ordering/comparison","You can determine relative position"]],"caption":"Binary Search Prerequisites Summary","headers":["Prerequisite","Formal Requirement","Intuitive Meaning"]},"type":"table"}],"titleType":"number","titleNumber":1},{"id":"mountain-problem","title":"The Mountain Problem — Where Binary Search Fails","content":[{"data":{"content":"Consider a seemingly straightforward problem: you're given an array of integers that first increases, then decreases—like a mountain profile. Your task is to find the peak (the maximum value). At first glance, this looks like a search problem. Can we use binary search?\n\nLet's think carefully. In a mountain array:\n- Elements to the left of the peak are *ascending*\n- Elements to the right of the peak are *descending*\n- The peak itself is greater than both its neighbors\n\n**The Monotonicity Violation**\n\nHere's where it gets interesting. A mountain array is *not* monotonic—it increases, then decreases. But there's a hidden monotonic property we can exploit:\n\n- If `arr[mid] < arr[mid + 1]`, the peak is to the right\n- If `arr[mid] > arr[mid + 1]`, the peak is at mid or to the left\n\nThis *is* a form of monotonicity! The predicate \"is mid part of the descending region?\" transitions from false to true exactly once. So binary search *does* work for finding the peak. Crisis averted—for this specific problem."},"type":"text"},{"data":{"fileName":"MountainPeak.java","languages":[{"code":"// Finding peak in a mountain array - binary search DOES work here\n// The hidden monotonic property: \"is this position in descending region?\"\n\nfunction findPeakInMountain(arr: number[]): number {\n let left = 0;\n let right = arr.length - 1;\n \n while (left < right) {\n const mid = left + Math.floor((right - left) / 2);\n \n if (arr[mid] < arr[mid + 1]) {\n // Still ascending - peak is to the right\n left = mid + 1;\n } else {\n // In descending region or at peak - answer is at mid or left\n right = mid;\n }\n }\n \n return left; // Returns the index of the peak\n}\n\n// Example: [1, 3, 8, 12, 4, 2]\n// ^ascending^ ^descending^\n// peak=12 at index 3\nconst mountain = [1, 3, 8, 12, 4, 2];\nconsole.log(findPeakInMountain(mountain)); // 3","label":"TypeScript","value":"typescript"},{"code":"# Finding peak in a mountain array - binary search DOES work here\n# The hidden monotonic property: \"is this position in descending region?\"\n\ndef find_peak_in_mountain(arr: list[int]) -> int:\n left = 0\n right = len(arr) - 1\n \n while left < right:\n mid = left + (right - left) // 2\n \n if arr[mid] < arr[mid + 1]:\n # Still ascending - peak is to the right\n left = mid + 1\n else:\n # In descending region or at peak - answer is at mid or left\n right = mid\n \n return left # Returns the index of the peak\n\n# Example: [1, 3, 8, 12, 4, 2]\n# ^ascending^ ^descending^\n# peak=12 at index 3\nmountain = [1, 3, 8, 12, 4, 2]\nprint(find_peak_in_mountain(mountain)) # 3","label":"Python","value":"python"}]},"type":"code"},{"data":{"icon":"Lightbulb","title":"Hidden Monotonicity","content":"The mountain peak problem teaches a valuable lesson: sometimes monotonicity is hidden. Even when the values themselves aren't monotonic, there may be a derived property (like 'is the slope positive?') that is monotonic. Finding this hidden monotonicity is a key skill in algorithm design.","variant":"tip"},"type":"callout"},{"data":{"content":"**But What If We Want the Maximum Value Over a Continuous Domain?**\n\nThe mountain peak problem worked because we had discrete elements and a hidden binary predicate. But consider a different scenario: you have a continuous function `f(x)` defined over the real interval `[a, b]`. The function first increases, reaches a maximum, then decreases. You want to find `x*` that maximizes `f(x)`.\n\nNow there's no discrete array. There's no \"next element\" to compare against. The function value at a point tells you the *height* at that point, but not directly whether you're left or right of the maximum. This is where binary search genuinely breaks down."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"continuous-optimization","title":"Continuous Optimization — A Fundamentally Different Problem","content":[{"data":{"content":"Let's formalize the class of problems where binary search fails but ternary search excels.\n\n**The Unimodal Function Optimization Problem**\n\nGiven a function `f: [a, b] → ℝ` that is:\n1. **Unimodal** — Has exactly one local maximum (or minimum) in `[a, b]`\n2. **Continuous** — No jumps or gaps\n3. **Single-peaked** — Strictly increasing before the peak, strictly decreasing after\n\nFind `x*` such that `f(x*)` is maximized.\n\n**Why Binary Search Fails**\n\nWith binary search, we'd pick a midpoint `m` and evaluate `f(m)`. But what does `f(m)` tell us?\n\n- If `f(m) = 10`, is the maximum to the left or right of `m`?\n- We can't tell! The value 10 could be on the ascending side (maximum is to the right) or the descending side (maximum is to the left) or *at* the maximum.\n\nBinary search requires comparing against something—a target value, a boundary, a neighbor. With a single function evaluation at a single point, we have no basis for eliminating either half."},"type":"text"},{"data":{"height":"350px","mermaidSyntax":"%%{init: {'theme': 'dark'}}%%\ngraph LR\n subgraph \"Binary Search\nSingle Point Problem\"\n A[\"Query f(m)\"]\n B[\"f(m) = 10\"]\n C[\"Left half?\nor\nRight half?\"]\n A --> B --> C\n C -.- D[\"❌ Cannot decide!\"]\n end\n \n subgraph \"Ternary Search\nTwo Points Solution\"\n E[\"Query f(m1) and f(m2)\"]\n F[\"f(m1) = 8, f(m2) = 12\"]\n G[\"Since f(m2) > f(m1)\nPeak is right of m1\"]\n E --> F --> G\n G -.- H[\"✅ Eliminate left third\"]\n end"},"type":"mermaid-excalidraw"},{"data":{"content":"**The Two-Point Comparison Insight**\n\nThe key insight is that we need *two* evaluation points to determine direction. If we query `f(m1)` and `f(m2)` where `m1 < m2`, then:\n\n- If `f(m1) < f(m2)`: The peak must be to the right of `m1` (we're still ascending at m1)\n- If `f(m1) > f(m2)`: The peak must be to the left of `m2` (we're already descending at m2)\n- If `f(m1) = f(m2)`: The peak is between `m1` and `m2` (both points are equidistant from peak in value)\n\nThis gives us a *decision rule*—but it can only eliminate roughly one-third of the search space per iteration, not half. This is the fundamental trade-off that defines ternary search: **we trade logarithmic base for applicability to a broader class of problems**."},"type":"text"},{"data":{"icon":"Info","title":"The Derivative Perspective","content":"If you know calculus, here's another view: finding the maximum of f(x) is equivalent to finding where f'(x) = 0 and transitions from positive to negative. The derivative f'(x) IS monotonic (positive → zero → negative) for a unimodal function. Binary search on f'(x) would work! But computing f'(x) requires computing f at nearby points—which brings us back to ternary search's two-point approach.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"real-world-scenarios","title":"Real-World Scenarios Without Monotonicity","content":[{"data":{"content":"$66"},"type":"text"},{"data":{"items":["**No Monotonicity** — Values increase then decrease (or vice versa), not consistently in one direction","**Continuous Domain** — Often searching over real numbers, not discrete elements","**Single Extremum** — Exactly one maximum or minimum in the search interval (unimodal)","**No Direct Comparison Target** — Unlike binary search, there's no specific value you're searching for","**Optimization Objective** — Goal is finding the best possible value, not checking existence or location of a specific element"],"title":{"icon":"AlertCircle","text":"Key Characteristics of Ternary Search Problems","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"rows":[["Find element in sorted array","✅ Yes","Overkill","Find 42 in [1,2,5,42,99]"],["Find first element ≥ target","✅ Yes","Overkill","Lower bound query"],["Find peak in mountain array","✅ Yes (hidden monotonicity)","Possible but slower","Max in [1,3,5,4,2]"],["Maximize f(x) where f is unimodal","❌ No","✅ Yes","Optimal learning rate"],["Minimize convex function","❌ No","✅ Yes","Least squares optimization"],["Find any peak in multi-modal function","❌ No","❌ No (need other approaches)","Multiple local maxima"]],"caption":"Binary Search vs. Ternary Search Problem Types","headers":["Problem Type","Binary Search?","Ternary Search?","Example"]},"type":"table"}],"titleType":"number","titleNumber":4},{"id":"geometry-of-problem","title":"The Geometry of the Problem","content":[{"data":{"content":"$67"},"type":"text"},{"data":{"content":"$68"},"type":"text"},{"data":{"icon":"Lightbulb","title":"Visualizing the Elimination","content":"Imagine a mountain. You stand at two points, m1 and m2, and measure your altitude at each. If you're higher at m2 than m1, you know the peak is to your right (since if the peak were left of m1, you'd be descending and m2 would be lower). You can safely eliminate everything to the left of m1 from consideration.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"common-misconceptions","title":"Common Misconceptions","content":[{"data":{"items":["**\"Ternary search is just binary search with three parts\"** — No. The fundamental difference is what information you get from queries. Binary search uses one comparison to eliminate half; ternary search uses two comparisons to eliminate one-third. They solve different problem classes.","**\"You can always use ternary search instead of binary search\"** — Technically true, but wasteful. For monotonic functions, binary search is strictly more efficient. Use the right tool for the right problem.","**\"Ternary search works on any function\"** — No. Ternary search requires unimodality. If a function has multiple peaks and valleys, ternary search will find *a* local extremum, but not necessarily the global one. It may also get stuck or return incorrect results.","**\"Binary search can't find maxima\"** — It can, when there's hidden monotonicity (like the mountain array example). The key is whether you can formulate a monotonic predicate.","**\"Ternary search is slower than binary search\"** — Yes, per iteration (2 comparisons vs 1), and it eliminates less per iteration (1/3 vs 1/2). But for unimodal functions without a usable monotonic predicate, it's *the right tool*."],"title":{"icon":"XCircle","text":"Misconceptions About Binary vs. Ternary Search","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"icon":"AlertCircle","title":"Know Your Problem Structure","content":"Before reaching for ternary search, always ask: is there hidden monotonicity I can exploit? Binary search on a clever predicate is preferable to ternary search when possible. Ternary search is the backup when monotonicity truly doesn't exist.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"practical-comparison","title":"A Practical Comparison Example","content":[{"data":{"content":"Let's compare approaches on a concrete problem to solidify understanding.\n\n**Problem:** Find the x-value that maximizes `f(x) = -(x - 5)² + 25` over the interval `[0, 10]`.\n\nThis is an inverted parabola with maximum at x = 5 where f(5) = 25."},"type":"text"},{"data":{"tabs":[{"id":"attempt-binary","badge":"❌ Fails","label":"Attempt: Binary Search","content":[{"data":{"languages":[{"code":"// Attempting binary search for maximum - THIS DOESN'T WORK\n\nfunction f(x: number): number {\n return -(x - 5) ** 2 + 25; // Max at x=5, f(5)=25\n}\n\nfunction attemptBinarySearch(left: number, right: number): number {\n while (right - left > 0.0001) {\n const mid = (left + right) / 2;\n const value = f(mid);\n \n // PROBLEM: What do we do with 'value'?\n // If f(mid) = 16, is the max left or right of mid?\n // - If mid = 1, max is to the RIGHT (ascending region)\n // - If mid = 9, max is to the LEFT (descending region)\n // We can't tell from just f(mid)!\n \n // Any choice we make here is arbitrary:\n if (value > 0) {\n left = mid; // ??? This doesn't make sense\n } else {\n right = mid; // ??? Neither does this\n }\n }\n return left;\n}\n\n// Binary search CANNOT solve this without additional information","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"icon":"XCircle","title":"Binary Search Fails","content":"A single evaluation f(mid) gives us the height at that point, but no information about which direction leads to higher values. We need to compare with another point to determine the slope.","variant":"error"},"type":"callout"}]},{"id":"correct-ternary","badge":"✅ Works","label":"Solution: Ternary Search","content":[{"data":{"languages":[{"code":"// Ternary search for maximum - CORRECT APPROACH\n\nfunction f(x: number): number {\n return -(x - 5) ** 2 + 25; // Max at x=5, f(5)=25\n}\n\nfunction ternarySearchMax(left: number, right: number): number {\n const epsilon = 1e-9;\n \n while (right - left > epsilon) {\n const m1 = left + (right - left) / 3;\n const m2 = right - (right - left) / 3;\n \n const f1 = f(m1);\n const f2 = f(m2);\n \n if (f1 < f2) {\n // f2 is higher, so max is to the right of m1\n left = m1;\n } else {\n // f1 is higher or equal, so max is to the left of m2\n right = m2;\n }\n \n // We've eliminated 1/3 of the search space\n }\n \n return (left + right) / 2;\n}\n\nconst result = ternarySearchMax(0, 10);\nconsole.log(`Maximum at x = ${result.toFixed(6)}`); // ~5.000000\nconsole.log(`f(x) = ${f(result).toFixed(6)}`); // ~25.000000","label":"TypeScript","value":"typescript"},{"code":"# Ternary search for maximum - CORRECT APPROACH\n\ndef f(x: float) -> float:\n return -(x - 5) ** 2 + 25 # Max at x=5, f(5)=25\n\ndef ternary_search_max(left: float, right: float) -> float:\n epsilon = 1e-9\n \n while right - left > epsilon:\n m1 = left + (right - left) / 3\n m2 = right - (right - left) / 3\n \n f1 = f(m1)\n f2 = f(m2)\n \n if f1 < f2:\n # f2 is higher, so max is to the right of m1\n left = m1\n else:\n # f1 is higher or equal, so max is to the left of m2\n right = m2\n \n # We've eliminated 1/3 of the search space\n \n return (left + right) / 2\n\nresult = ternary_search_max(0, 10)\nprint(f\"Maximum at x = {result:.6f}\") # ~5.000000\nprint(f\"f(x) = {f(result):.6f}\") # ~25.000000","label":"Python","value":"python"}]},"type":"code"},{"data":{"icon":"CheckCircle","title":"Ternary Search Succeeds","content":"By comparing f(m1) and f(m2), we determine which side of the interval contains points with higher values. We can then safely eliminate the side with lower values, shrinking our search space by 1/3 each iteration.","variant":"success"},"type":"callout"}]}],"defaultTab":"attempt-binary"},"type":"tabs"}],"titleType":"number","titleNumber":7},{"id":"summary-path-forward","title":"Summary: When to Look Beyond Binary Search","content":[{"data":{"content":"We've explored the boundaries of binary search and the class of problems that require a different approach. Here are the key takeaways:"},"type":"text"},{"data":{"type":"ordered","items":["**Binary search requires monotonicity** — There must be a single transition point where a predicate changes from false to true (or ascending to descending with a clear boundary).","**Single-point queries are insufficient for optimization** — Without a comparison target or neighbor, a function value tells you height but not direction.","**Two-point comparisons enable direction detection** — Comparing f(m1) and f(m2) tells us which direction leads to higher (or lower) values.","**Ternary search trades efficiency for applicability** — It eliminates 1/3 per iteration instead of 1/2, but works on problems binary search can't handle.","**Unimodality is essential** — Ternary search requires exactly one maximum (or minimum) in the search interval.","**Look for hidden monotonicity first** — If you can formulate a monotonic predicate, binary search is more efficient. Ternary search is the backup."],"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 we understand when binary search fails, we'll dive deep into the structure that makes ternary search possible: unimodal functions. The next page explores what makes a function unimodal, how to recognize this property in problems, and why unimodality is both necessary and sufficient for ternary search to work correctly."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the fundamental limitations of binary search and have been introduced to the class of problems where ternary search applies. Next, we'll explore unimodal functions in depth—the mathematical foundation that makes ternary search work.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_3dabc4b4ecaf7831900282520179412d","title":"Unimodal Functions","order":1,"content":null,"isLocked":true},{"id":"seed_20cbf46fd6945cf50144cd94aea0a8df","title":"Finding Maximum/Minimum of Unimodal Functions","order":2,"content":null,"isLocked":true},{"id":"seed_078046ee82aa6d8cd79fabd5ab429018","title":"Comparison with Binary Search","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792318333826,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"ternary-search"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"ternary-search\"},\"type\":\"query\"}]"},{"dehydratedAt":1792318333937,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792318333933,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_4789e379a0d1c65efe5ba1334a08e596"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_4789e379a0d1c65efe5ba1334a08e596\"},\"type\":\"query\"}]"},{"dehydratedAt":1792318333937,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792318333935,"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_3dabc4b4ecaf7831900282520179412d"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_3dabc4b4ecaf7831900282520179412d\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792318333937,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792318333935,"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_3dabc4b4ecaf7831900282520179412d"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_3dabc4b4ecaf7831900282520179412d\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792318333937,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792318333935,"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_3dabc4b4ecaf7831900282520179412d"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_3dabc4b4ecaf7831900282520179412d\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792318333937,"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_3dabc4b4ecaf7831900282520179412d","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_3dabc4b4ecaf7831900282520179412d\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@69"}]},"children":"$L6a"}]