Ternary Search: Algorithm Deep Dive

1. Introduction and Core Concepts

Ternary search is a divide-and-conquer searching technique that extends the familiar binary search paradigm by dividing the search space into three parts instead of two. While binary search splits a sorted array at a single midpoint, ternary search evaluates two midpoints that partition the interval into thirds, then discards the third that cannot contain the target. This elegant generalization makes it a powerful tool not only for searching in sorted arrays but, more importantly, for optimizing unimodal functions where binary search cannot be applied directly.

At its core, ternary search operates on two distinct problem domains. The first is the classic search in a sorted array, where the goal is to determine whether a target value exists and return its index. In this context, it is a direct analogue of binary search and shares the same prerequisite: the input must be sorted. The second and more compelling domain is optimization of unimodal functions — functions that strictly increase to a single peak (or decrease to a single valley) and then strictly decrease. For this class of problems, ternary search is often the most intuitive and efficient approach, capable of finding the maximum or minimum without requiring derivatives.

Understanding ternary search matters because it illuminates a fundamental trade-off in algorithm design: reducing the number of iterations versus increasing the work per iteration. Although ternary search theoretically requires fewer iterations than binary search to shrink the search space to a single element, it performs more comparisons per iteration. This nuance teaches a critical lesson that asymptotic complexity alone does not determine real-world performance. Furthermore, the optimization variant of ternary search is indispensable in competitive programming, numerical methods, machine learning hyperparameter tuning, and any scenario where you need to find an optimum of a convex or concave function efficiently.

Prerequisites and Key Properties

For the sorted-array variant, the array must be sorted in either ascending or descending order and allow random access. For the optimization variant, the function must be strictly unimodal on the search interval. This means there exists a single point m such that the function is monotonically increasing on [left, m] and monotonically decreasing on [m, right] for a maximum, or the reverse for a minimum. If the function is not unimodal or has plateaus, ternary search may converge to a local optimum or fail to terminate correctly.

Unlike binary search, which has a recurrence of T(n) = T(n/2) + O(1), ternary search follows T(n) = T(n/3) + O(1) for the search variant, leading to a logarithmic base of 3. However, the constant factor is larger due to two comparisons per step. This makes ternary search an excellent case study for analyzing how mathematical elegance translates into practical engineering decisions.

2. How It Works

The mechanism of ternary search is best understood by visualizing the search interval [low, high]. Instead of computing one middle index, we compute two partition points that divide the interval into three equal segments. Mathematically, these points are defined as mid1 = low + (high - low) / 3 and mid2 = high - (high - low) / 3. For integer arrays, integer division is used, while for continuous functions, floating-point arithmetic is employed. These two points create three regions: [low, mid1], [mid1, mid2], and [mid2, high].

In the sorted-array search, we compare the target value with the elements at mid1 and mid2. There are four possible outcomes. If the target equals arr[mid1] or arr[mid2], we have found it and return the index immediately. If the target is less than arr[mid1], we know from the sorted property that it must lie in the left third, so we set high = mid1 - 1. If the target is greater than arr[mid2], it must be in the right third, so we set low = mid2 + 1. Otherwise, the target is strictly between arr[mid1] and arr[mid2], and we can discard both outer thirds by setting low = mid1 + 1 and high = mid2 - 1. This process repeats until the interval is empty or the target is found.

For unimodal function optimization, the logic is subtly different and relies on comparing function values rather than searching for equality. To find the maximum of a unimodal function f, we evaluate f(mid1) and f(mid2). If f(mid1) < f(mid2), the peak cannot be in the left third [low, mid1] because the function is still rising at mid1, so we discard it by setting low = mid1. Conversely, if f(mid1) > f(mid2), the function has already started decreasing by mid2, so the peak cannot be in the right third [mid2, high] and we set high = mid2. If the values are equal, we can shrink from both sides. By repeatedly discarding one-third of the interval, the interval converges to the optimum point with high precision.

Why Three Partitions?

The choice of three partitions is not arbitrary. For optimization, two points are the minimum needed to determine the slope direction of a unimodal function. A single midpoint provides no information about whether the peak lies to the left or right. With two interior points, their relative values reveal the trend. While you could divide into four or more parts, three is optimal in terms of minimizing function evaluations per iteration for this class of search. This principle is closely related to the golden-section search, which is a more optimized variant that reuses function evaluations.

It is important to distinguish discrete ternary search on arrays from continuous ternary search on real-valued functions. The discrete version terminates when low > high or when the interval size is small enough to scan linearly. The continuous version terminates when high - low < epsilon, where epsilon is the desired precision, such as 1e-9. The continuous version never checks for equality but instead narrows the interval until it is sufficiently small, then returns the midpoint as the approximate optimum.

3. Implementation

Implementing ternary search correctly requires careful handling of indices, termination conditions, and edge cases. Below are four production-ready Python implementations covering the most common use cases, with detailed comments and proper handling of integer overflow and floating-point precision.

The first implementation is the iterative version for searching in a sorted array. This is the most practical variant for general software engineering because it avoids recursion overhead and is easy to reason about. Note how we compute mid1 and mid2 to avoid integer overflow, a classic bug when using (low + high) // 3 on large arrays in languages like Java or C++.

def ternary_search_iterative(arr, target):
    # arr must be sorted in ascending order
    low = 0
    high = len(arr) - 1
    while low <= high:
        # Divide range into three parts to avoid overflow
        mid1 = low + (high - low) // 3
        mid2 = high - (high - low) // 3
        
        if arr[mid1] == target:
            return mid1
        if arr[mid2] == target:
            return mid2
            
        # Narrow search space to one third
        if target < arr[mid1]:
            high = mid1 - 1
        elif target > arr[mid2]:
            low = mid2 + 1
        else:
            # target is between mid1 and mid2
            low = mid1 + 1
            high = mid2 - 1
    return -1  # not found

The recursive formulation is more declarative and mirrors the mathematical recurrence directly. While elegant, it incurs O(log3 n) stack space and may hit recursion limits in Python for very large arrays. It is excellent for interviews and educational purposes where clarity is prioritized over micro-optimization.

def ternary_search_recursive(arr, target, low, high):
    # Base case: search space exhausted
    if low > high:
        return -1
    
    mid1 = low + (high - low) // 3
    mid2 = high - (high - low) // 3
    
    if arr[mid1] == target:
        return mid1
    if arr[mid2] == target:
        return mid2
    
    if target < arr[mid1]:
        return ternary_search_recursive(arr, target, low, mid1 - 1)
    elif target > arr[mid2]:
        return ternary_search_recursive(arr, target, mid2 + 1, high)
    else:
        return ternary_search_recursive(arr, target, mid1 + 1, mid2 - 1)

# Wrapper for cleaner API
def ternary_search(arr, target):
    return ternary_search_recursive(arr, target, 0, len(arr) - 1)

The third implementation solves the more powerful optimization problem: finding the maximum of a unimodal function on a continuous interval. This version is widely used in numerical computing and competitive programming. The epsilon parameter controls the absolute precision of the result. For finding a minimum, simply reverse the comparison from < to >.

def ternary_search_unimodal(func, left, right, epsilon=1e-9):
    """
    Find maximum of unimodal function func on interval [left, right].
    Unimodal means strictly increasing then strictly decreasing.
    For minimum, reverse comparison.
    """
    while right - left > epsilon:
        mid1 = left + (right - left) / 3
        mid2 = right - (right - left) / 3
        
        # Compare function values to discard one third
        if func(mid1) < func(mid2):
            # Maximum lies in [mid1, right]
            left = mid1
        else:
            # Maximum lies in [left, mid2]
            right = mid2
    
    return (left + right) / 2

# Example: find peak of f(x) = -(x-3)**2 + 9
def f(x):
    return -(x - 3) ** 2 + 9

peak_x = ternary_search_unimodal(f, 0, 6)
print(f"Peak at x = {peak_x:.6f}, f(x) = {f(peak_x):.6f}")

The final implementation handles the discrete unimodal array case — finding the peak element in an array that first increases and then decreases, such as [1, 4, 9, 15, 22, 18, 13, 6]. This is a common interview problem often called the bitonic or mountain array problem. The algorithm narrows the search until only 2-3 elements remain, then performs a linear scan to avoid infinite loops due to integer division.

from typing import List, Callable

def ternary_search_max_integer(arr: List[int]) -> int:
    """
    Find index of maximum in unimodal array (increasing then decreasing).
    Example: [1, 3, 8, 12, 7, 4, 2] -> index 3
    """
    low = 0
    high = len(arr) - 1
    
    while high - low > 2:
        mid1 = low + (high - low) // 3
        mid2 = high - (high - low) // 3
        
        if arr[mid1] < arr[mid2]:
            # Peak is to the right of mid1
            low = mid1 + 1
        elif arr[mid1] > arr[mid2]:
            # Peak is to the left of mid2
            high = mid2 - 1
        else:
            # Equal values, shrink both sides
            low = mid1 + 1
            high = mid2 - 1
    
    # Linear scan remaining 2-3 elements
    max_idx = low
    for i in range(low + 1, high + 1):
        if arr[i] > arr[max_idx]:
            max_idx = i
    return max_idx

# Test
unimodal = [1, 4, 9, 15, 22, 18, 13, 6]
print(ternary_search_max_integer(unimodal))  # Expected: 4

4. Step-by-Step Example

To solidify the mechanics, let us walk through a concrete example of ternary search on a sorted array. Consider the sorted array arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] with n = 10 elements, and our target is 23. We will trace the iterative algorithm step by step.

Iteration 1: low = 0, high = 9. We compute mid1 = 0 + (9 - 0) // 3 = 3, and mid2 = 9 - (9 - 0) // 3 = 6. Thus arr[mid1] = arr[3] = 12 and arr[mid2] = arr[6] = 38. We compare target 23 with both. Since 23 != 12 and 23 != 38, we check the range. 23 is not less than 12, and not greater than 38, so it must lie between them. We therefore set low = mid1 + 1 = 4 and high = mid2 - 1 = 5. The search space shrinks from 10 elements to just [16, 23].

Iteration 2: Now low = 4, high = 5. Compute mid1 = 4 + (5 - 4) // 3 = 4, and mid2 = 5 - (5 - 4) // 3 = 5. So arr[mid1] = 16 and arr[mid2] = 23. On the second comparison, arr[mid2] == 23, so we immediately return index 5. The search succeeded in just 2 iterations, examining 4 elements total.

Now consider an optimization example to show the continuous variant. Let f(x) = - (x - 4)^2 + 16, a parabola with maximum at x = 4, and search interval [0, 8] with epsilon = 0.1. Iteration 1: mid1 = 0 + 8/3 = 2.66, mid2 = 8 - 8/3 = 5.33. f(mid1) = -1.77 + 16 = 14.22, f(mid2) = -1.77 + 16 = 14.22. Since they are equal, we could set low = 2.66 and high = 5.33. Iteration 2: mid1 = 2.66 + (5.33-2.66)/3 = 3.55, mid2 = 5.33 - (5.33-2.66)/3 = 4.44. f(3.55) = 15.79, f(4.44) = 15.80. Since f(mid1) < f(mid2), we set low = 3.55. The interval is now [3.55, 5.33], already tightly bracketing the true peak at 4. After a few more iterations, the interval width falls below 0.1 and we return approximately 4.0.

Trace Table for Sorted Search

For visual learners, the following trace summarizes the first example. Notice how the interval size reduces by roughly two-thirds each time, not one-half as in binary search.

• Start: low=0, high=9, size=10, mid1=3 (12), mid2=6 (38) → target between → new range [4,5]
• Step 2: low=4, high=5, size=2, mid1=4 (16), mid2=5 (23) → found at mid2
• If target were 91, the trace would be: [0,9] → [7,9] → [8,9] → found, taking 3 iterations versus 4 for binary search in worst case

This walkthrough highlights a key practical point: ternary search reduces iterations but not necessarily total comparisons. In iteration 1 we performed 4 comparisons (two equalities and two range checks), whereas binary search would have performed at most 2. Over many iterations, this extra work can outweigh the benefit of fewer iterations.

5. Complexity Analysis

Complexity analysis of ternary search reveals why it is theoretically elegant but often slower in practice for sorted-array searching. The analysis differs between the discrete search variant and the continuous optimization variant, and between iterative and recursive implementations.

For searching in a sorted array of size n, the recurrence relation is T(n) = T(n/3) + 4 * O(1), because we perform up to four comparisons and reduce the problem to one-third of its size. By the Master Theorem, this solves to T(n) = O(log3 n). Since log3 n = log2 n / log2 3 ≈ 0.63 * log2 n, ternary search uses about 37% fewer iterations than binary search. However, each iteration does more work. A precise comparison counts comparisons: binary search does 1-2 comparisons per iteration for O(log2 n) iterations, totaling ≈ log2 n comparisons. Ternary search does 2-4 comparisons per iteration for O(log3 n) iterations, totaling ≈ 2 * log3 n ≈ 1.26 * log2 n comparisons. Thus, ternary search typically performs about 26% more comparisons overall.

For unimodal function optimization on a continuous interval of length R with precision epsilon, the number of iterations is O(log((R)/epsilon) / log(3/2)) if we discard one-third each time, or more precisely O(log_{3/2}(R/epsilon)). Some analyses simplify this to O(log(R/epsilon)). Each iteration requires two function evaluations, so total function evaluations is 2 * iterations. This is the dominant cost when function evaluation is expensive, which is why golden-section search, which reuses one evaluation per iteration, is often preferred in numerical optimization.

Space complexity is O(1) for the iterative implementation, as it uses only a few integer variables. The recursive implementation uses O(log3 n) stack space due to recursion depth. There is no significant difference in best, average, and worst cases for time complexity in terms of Big O — all are logarithmic — but the exact number of comparisons varies. The best case is O(1) when the target is at mid1 or mid2 on the first iteration. The worst case occurs when the target is absent or at the extremes, requiring full narrowing.

Why Big O Can Be Misleading

Both binary and ternary search are O(log n), so asymptotic notation hides the constant factors that determine real performance. In practice, binary search is almost always faster for array searching due to fewer comparisons, better branch prediction, and better cache locality with simpler code. Ternary search shines not where it competes with binary search, but where binary search cannot be applied — namely, optimization of unimodal functions without derivatives. Understanding this distinction is crucial for selecting the right tool.

6. Variations and Optimizations

Several variations of ternary search optimize its performance or adapt it to specific constraints. The most important optimization for continuous optimization is the golden-section search, which is essentially an optimized ternary search that minimizes function evaluations.

Golden-section search uses partition points based on the golden ratio φ = (1 + sqrt(5))/2 ≈ 1.618 instead of 1/3 and 2/3. The key advantage is that one of the interior points from the previous iteration can be reused in the next iteration, so only one new function evaluation is needed per iteration after the first, compared to two for standard ternary search. For expensive functions, this nearly halves the total cost. The interval reduction factor per iteration is 0.618 instead of 0.666, so it converges slightly slower per iteration but faster per function evaluation.

Another practical optimization is the hybrid approach for discrete arrays: when the remaining interval becomes small (e.g., fewer than 30 elements), switch to linear search or binary search. This avoids the overhead of computing two midpoints and performing multiple branches when a simple scan would be faster and more cache-friendly. Similarly, for integer unimodal arrays, the final linear scan over 2-3 elements as shown in the code above prevents infinite loops caused by integer division where mid1 and mid2 stop moving.

For parallel architectures, ternary search can be parallelized more effectively than binary search. Since the two midpoint comparisons are independent, they can be evaluated concurrently on two cores or via SIMD instructions. In theory, with two parallel comparators, the wall-clock time per iteration is the same as binary search, but with a larger reduction factor, leading to a genuine speedup. This is relevant in hardware implementations and GPU-based searches.

Handling Edge Cases and Duplicates

Standard ternary search assumes distinct elements or a strictly unimodal function. With duplicates in a sorted array, the algorithm still works but may return any matching index, not necessarily the first or last occurrence. To find boundaries, you need to modify the logic to continue searching after a match, similar to lower_bound and upper_bound variants of binary search. For non-strictly unimodal functions with plateaus, the condition f(mid1) == f(mid2) requires special handling — shrinking both sides as shown in the integer peak code prevents getting stuck.

An alternative variation is k-ary search, which generalizes to k partitions. Ternary search is k=3. As k increases, iterations decrease as O(log_k n) but comparisons per iteration increase as O(k). Research shows that for in-memory array search, k=2 (binary search) is optimal for minimizing comparisons, while for external memory or network searches where the cost of probing is high, larger k can be beneficial.

7. Real-World Applications

While ternary search is rarely used for simple sorted-array lookups in production systems — where binary search, hash tables, or B-trees dominate — its optimization variant is widely applicable in real-world systems where the objective function is unimodal and derivative-free optimization is needed.

In web servers and load balancing, ternary search can optimize resource allocation. For example, determining the optimal number of worker threads or cache size often yields a unimodal throughput curve: too few threads underutilize CPU, too many cause contention and context-switch overhead, with a single peak in between. By treating throughput as a unimodal function of thread count and performing ternary search over the integer parameter space, an auto-tuner can find the optimum in O(log n) load tests instead of O(n) exhaustive testing.

In databases and networks, ternary search appears in query optimization and congestion control. Database query optimizers may use it to find the optimal join order cost or memory allocation where cost is convex. In TCP congestion control and rate limiting, the relationship between sending rate and goodput is often unimodal — increasing rate improves throughput until packet loss dominates — and ternary search can help find the optimal rate without gradient information. Content Delivery Networks (CDNs) use similar techniques to find the optimal chunk size for video streaming that minimizes rebuffering.

In machine learning and data science, ternary search is used for hyperparameter tuning of single unimodal parameters, such as finding the optimal learning rate, regularization strength, or decision threshold that maximizes validation accuracy. When the validation metric as a function of the hyperparameter is unimodal and each evaluation requires training a model, minimizing the number of evaluations via ternary search saves significant compute. It is also used in computer graphics for finding the closest point on a convex curve and in computational geometry for ternary search on the answer (e.g., minimizing maximum distance).

When Not to Use Ternary Search

Ternary search is not suitable for general sorted-array searching in databases or file systems where binary search or interpolation search is faster and simpler. It is also inappropriate when the function is not unimodal, is noisy, or has multiple peaks — in those cases, hill climbing, simulated annealing, or gradient-based methods are needed. For high-dimensional optimization, ternary search does not generalize well; methods like gradient descent or Nelder-Mead are preferred.

8. Comparison with Alternatives

Choosing the right search algorithm requires understanding the trade-offs between time complexity, prerequisites, and practical performance. Ternary search occupies a unique niche: it is not the best general-purpose search for sorted arrays, but it is the go-to for derivative-free unimodal optimization.

For sorted-array searching, linear search is O(n) and only suitable for small or unsorted data. Binary search is the gold standard with O(log2 n) time, O(1) space, and minimal comparisons. Interpolation search can achieve O(log log n) on uniformly distributed data but degrades to O(n) on skewed data and requires arithmetic on values. Jump search and exponential search are useful when random access is expensive or the array size is unknown. Ternary search, with O(log3 n) iterations but more comparisons, is theoretically competitive but practically slower than binary search for this task due to higher constant factors and more complex branching.

For optimization, the alternatives are more nuanced. Binary search cannot directly optimize unimodal functions without derivatives. Golden-section search is the closest competitor and is generally superior to ternary search for continuous optimization because it reuses evaluations. Hill climbing and gradient descent require derivatives or are susceptible to local optima. For discrete peak finding, binary search can also find a peak in O(log n) by comparing mid with neighbors, and is often simpler than ternary search for that specific problem.

Key Takeaway

Use binary search for sorted-array lookups. Use ternary search when you need to find the maximum or minimum of a unimodal function and you cannot or do not want to compute derivatives. If function evaluations are very expensive, prefer golden-section search over plain ternary search. For peak finding in a mountain array, both binary and ternary search work in O(log n), but binary search with neighbor comparison is often more concise.

9. Common Mistakes and Best Practices

Implementing ternary search correctly is surprisingly error-prone, especially for beginners who confuse the array-search and optimization variants. The most common mistakes stem from incorrect interval updates, improper termination conditions, and applying the algorithm to non-unimodal data.

A frequent bug is incorrect calculation of mid1 and mid2 with integer division leading to infinite loops. For example, using mid1 = (low + high) // 3 and mid2 = 2 * (low + high) // 3 is wrong and can cause mid1 == mid2 when the interval is small. The correct formulas are mid1 = low + (high - low) // 3 and mid2 = high - (high - low) // 3, which guarantee mid1 < mid2 and proper partitioning even for small intervals. Another common error is updating low and high incorrectly: after determining the target is between mid1 and mid2, some implementations set low = mid1 and high = mid2, which fails to exclude the already-checked midpoints and can cause infinite loops. The correct update is low = mid1 + 1 and high = mid2 - 1 for discrete search.

For continuous optimization, a critical mistake is using == to compare floating-point function values or using an inappropriate epsilon. Floating-point equality is unreliable; instead, compare with < and > and terminate based on interval width. Choosing epsilon too small can cause excessive iterations or non-termination due to floating-point precision limits, while too large yields inaccurate results. A best practice is to iterate a fixed number of times (e.g., 100-200 iterations) instead of checking epsilon, since the interval shrinks exponentially and 100 iterations gives precision far beyond double precision.

Applying ternary search to non-unimodal functions is a logical error that leads to wrong answers without any runtime error. Always verify unimodality before using it. For array search, forgetting to ensure the array is sorted is a similar pitfall. Additionally, many developers forget that ternary search on sorted arrays is not stable and does not guarantee the first occurrence with duplicates — explicit handling is needed for lower/upper bound queries.

Best Practices Checklist

• Verify prerequisites: sorted array for search, strictly unimodal function for optimization.
• Use overflow-safe midpoint formulas: low + (high - low) // 3 and high - (high - low) // 3.
• For discrete search, exclude midpoints after checking: low = mid1 + 1, high = mid2 - 1.
• For continuous search, terminate on interval width or fixed iterations, not function value equality.
• Handle small intervals explicitly: when high - low <= 2, do a linear scan to avoid infinite loops.
• Prefer iterative over recursive to avoid stack overflow and improve performance in Python.
• Consider golden-section search if function evaluations are expensive.
• Test edge cases: empty array, single element, target at boundaries, not found, plateau functions.
• Document whether you are searching for maximum or minimum and ensure comparison direction matches.

Finally, always benchmark against binary search for array searching. In most production environments, binary search will be faster and simpler. Reserve ternary search for its strength: optimization. When you do use it for optimization, clearly comment the unimodality assumption and the choice of epsilon or iteration count so future maintainers understand the convergence guarantee.

10. Interview Questions

Ternary search is a favorite in technical interviews because it tests understanding of divide-and-conquer, complexity analysis, and the ability to distinguish between searching and optimization. Below are common questions with guidance on expected answers.

Q1: Implement ternary search for a sorted array and analyze its complexity. How does it compare to binary search?

Expected answer: Provide iterative or recursive code as shown in Section 3, with correct midpoint calculation and interval updates. State time complexity O(log3 n) and space O(1) iterative, O(log3 n) recursive. Explain that while it uses fewer iterations than binary search (log3 n vs log2 n), it does more comparisons per iteration (up to 4 vs 2), so total comparisons are ~1.26 * log2 n, making it slower in practice for array search. Mention that both are O(log n) asymptotically, so the difference is constant factors and branch prediction.

Q2: Given a unimodal array like [1, 3, 8, 12, 4, 2], find the peak element. Can you do it in O(log n)?

Expected answer: Yes, using ternary search for peak finding. Compare arr[mid1] and arr[mid2]; if arr[mid1] < arr[mid2], peak is to the right, so low = mid1 + 1, else high = mid2 - 1. Alternatively, a binary search approach works too: compare arr[mid] with arr[mid+1]; if arr[mid] < arr[mid+1], peak is right, else left. Both are O(log n). Discuss handling of edge cases and why the array must be unimodal (increasing then decreasing) for this to work. Provide code and mention the final linear scan for 2-3 elements.

Q3: How would you find the maximum of a unimodal function f(x) on [l, r] without using derivatives?

Expected answer: Use ternary search on the continuous domain. Evaluate f at mid1 and mid2; if f(mid1) < f(mid2), maximum is in [mid1, r], else in [l, mid2]. Repeat until r - l < epsilon. Complexity O(log((r-l)/epsilon)). Mention that this requires strict unimodality and that for minimum, the comparison is reversed. Discuss precision trade-offs and the alternative of golden-section search which reuses one evaluation per iteration and is more efficient when f is expensive.

Q4: Why is ternary search not commonly used for searching in sorted arrays in standard libraries?

Expected answer: Because binary search is faster in practice despite having a slightly larger Big O base. Ternary search does more comparisons per iteration and has more complex branching, leading to worse cache performance and branch misprediction. Standard libraries prioritize practical speed and simplicity, so they use binary search. Ternary search's real value is in optimization, not in sorted-array search, where it is mainly of theoretical interest.

Q5: What happens if you apply ternary search to a function that is not unimodal, e.g., with two peaks?

Expected answer: The algorithm may converge to a local optimum or discard the interval containing the global optimum, returning an incorrect result. Ternary search's correctness proof relies on unimodality to guarantee that discarding one-third never discards the peak. With multiple peaks, the comparison f(mid1) < f(mid2) does not reliably indicate which side contains the global maximum. For multimodal functions, you need global optimization techniques like ternary search with multiple starts, simulated annealing, or evolutionary algorithms.

Preparing for these questions involves not just memorizing code but understanding the underlying invariants and trade-offs. Practice tracing the algorithm on paper, analyzing the recurrence, and articulating when to choose ternary search over binary search or golden-section search.