15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Ternary search finds the maximum of a strictly unimodal array, one that strictly rises to a single peak and then strictly falls. It compares two interior points, m1 and m2, and discards the outer part that cannot hold the peak. It takes O(log n) time and O(1) extra space. It is not the ternary search tree.
| Input | Nonempty, strictly unimodal array: one peak, no plateau |
|---|---|
| Split points | m1 = low + (high - low) // 3, m2 = high - (high - low) // 3 |
| Discard rule | A[m1] < A[m2]: low = m1 + 1. A[m1] > A[m2]: high = m2 - 1 |
| Time | O(log n), about log base 3/2 of n reductions |
| Extra space | O(1) |
| Finish | Scan the last one or two indices directly |
Ternary search here locates the maximum in a nonempty strictly unimodal array.
A strictly unimodal array has exactly one peak:
For example:
[1, 3] has its peak at index 1.[3, 1] has its peak at index 0.[1, 3, 3, 2] is not strictly unimodal because the maximum is a plateau.The method uses binary-search-style interval reduction with two interior split points:
The candidate interval is inclusive: [low, high].
Return an index of the unique maximum.
Use this array throughout the lesson.
1index: 0 1 2 3 4 5
2A: 1 4 7 9 6 2The values rise from 1 to 9, then fall from 9 to 2.
11 → 4 → 7 → 9 → 6 → 2
2 peakThe unique maximum is 9 at index 3.
Start with every index as a possible peak location:
1low = 0
2high = 5
3
4candidate interval = [0, 5]Divide the interval into roughly three parts.
1m1 = 0 + (5 - 0) // 3 = 1
2m2 = 5 - (5 - 0) // 3 = 4The inspected values are:
1A[m1] = A[1] = 4
2A[m2] = A[4] = 6Since 4 < 6, the peak cannot be at index 1 or anywhere to its left. Keep:
1[2, 5]The table shows each reduction before the final direct scan.
| State | low | high | m1 and value | m2 and value | Decision | New candidate interval |
|---|---|---|---|---|---|---|
| 0 | 0 | 5 | m1 = 1, A[1] = 4 | m2 = 4, A[4] = 6 | 4 < 6 | [2, 5] |
| 1 | 2 | 5 | m1 = 3, A[3] = 9 | m2 = 4, A[4] = 6 | 9 > 6 | [2, 3] |
| 2 | 2 | 3 | final scan | final scan | compare 7 and 9 | index 3 |
| 3 | — | — | — | — | return | index 3, value 9 |
Change the interval one boundary at a time.
1low = 0
2high = 5
3m1 = 1
4m2 = 4Peak of [1, 4, 7, 9, 6, 2]: m1 = 1, m2 = 4 and 4 < 6 gives [2, 5]; m1 = 3, m2 = 4 and 9 > 6 gives [2, 3]; comparing 7 and 9 returns index 3.
Compare:
1A[1] = 4
2A[4] = 6
34 < 6The peak must be to the right of m1.
Change only low:
1low = m1 + 1 = 2
2high = 5The new interval is:
1[2, 5]Calculate new split points inside [2, 5].
1m1 = 2 + (5 - 2) // 3 = 3
2m2 = 5 - (5 - 2) // 3 = 4Compare:
1A[3] = 9
2A[4] = 6
39 > 6The peak must be to the left of m2.
Change only high:
1low = 2
2high = m2 - 1 = 3The new interval is:
1[2, 3]Two candidates remain.
Compare both values directly:
17 < 9Index 3 holds the larger value.
The following fact guides both decisions:
At the start of each reduction step, the unique maximum of the strictly unimodal array lies within the inclusive candidate interval
[low, high].
That fact is the loop invariant.
At the start:
1[low, high] = [0, 5]The interval contains every index, including the maximum at index 3.
After State 0:
1[low, high] = [2, 5]Index 3 is still present.
After State 1:
1[low, high] = [2, 3]Index 3 is still present.
Discarded positions cannot contain the maximum because of strict unimodality.
Keep reducing while more than two candidate indices remain. A two-element interval is small enough to scan directly.
For the current inclusive interval [low, high]:
A[m1] and A[m2].The comparison outcomes determine which portion to discard.
A[m1] < A[m2]The peak cannot be at m1 or to its left.
If the peak were at or left of m1, then both m1 and m2 would be on the strictly decreasing side, or m1 would itself be the peak. In either case, because m1 < m2, we would have:
1A[m1] > A[m2]The result conflicts with A[m1] < A[m2].
Discard indices through m1:
1low = m1 + 1Do not set low = m2. The peak can lie between m1 and m2.
A[m1] > A[m2]The peak cannot be at m2 or to its right.
If the peak were at or right of m2, then both split points would be on the strictly increasing side, or m2 would itself be the peak. Since m1 < m2, that would require:
1A[m1] < A[m2]The result conflicts with A[m1] > A[m2].
Discard indices from m2 onward:
1high = m2 - 1A[m1] == A[m2]Equality has no meaning under this method.
With a strictly unimodal array and two distinct split indices, equality cannot occur. Equality indicates that the input may have a plateau, such as:
1[1, 3, 3, 2]Plateau behavior needs a separately specified policy. It is outside the method’s precondition.
Input: A, a nonempty array whose values strictly increase to one unique maximum and strictly decrease afterward.
Return value: An index of the unique maximum.
Mutation behavior: Does not modify A.
Boundary convention: low and high are inclusive indices.
Helper contract: indexOfMaximumInRange(A, start, end) examines every index from start through end, inclusive, and returns an index holding the largest value in that range. It does not modify A.
11 function peakIndexStrictUnimodal(A):
22 low = 0
33 high = length(A) - 1
44
55 while high - low + 1 > 2:
66 m1 = low + (high - low) // 3
77 m2 = high - (high - low) // 3
88
99 if A[m1] < A[m2]:
1010 low = m1 + 1
1111 else if A[m1] > A[m2]:
1212 high = m2 - 1
1313 else:
1414 report "input violates the strict-unimodal precondition"
1515
1616 return indexOfMaximumInRange(A, low, high)The loop stops once the interval has at most 2 indices. During a reduction step, m1 < m2. The final scan handles one or two remaining candidates.
1function indexOfMaximumInRange(A, start, end):
2 best = start
3
4 for i from start + 1 through end:
5 if A[i] > A[best]:
6 best = i
7
8 return bestUse the original array.
1index: 0 1 2 3 4 5
2A: 1 4 7 9 6 2Line 2
1low = 0Line 3
1high = 5Line 5
1high - low + 1 = 5 - 0 + 1 = 6
26 > 2Enter the loop.
Line 6
1m1 = 0 + (5 - 0) // 3
2m1 = 0 + 1
3m1 = 1Line 7
1m2 = 5 - (5 - 0) // 3
2m2 = 5 - 1
3m2 = 4Line 9
1A[m1] < A[m2]
2A[1] < A[4]
34 < 6The condition is true.
Line 10
1low = m1 + 1
2low = 2Current state:
1low = 2
2high = 5
3candidate interval = [2, 5]Line 5
1high - low + 1 = 5 - 2 + 1 = 4
24 > 2Enter the loop.
Line 6
1m1 = 2 + (5 - 2) // 3
2m1 = 2 + 1
3m1 = 3Line 7
1m2 = 5 - (5 - 2) // 3
2m2 = 5 - 1
3m2 = 4Line 9
1A[3] < A[4]
29 < 6The condition is false.
Line 11
1A[3] > A[4]
29 > 6The condition is true.
Line 12
1high = m2 - 1
2high = 3Current state:
1low = 2
2high = 3
3candidate interval = [2, 3]Line 5
1high - low + 1 = 3 - 2 + 1 = 2
22 > 2The condition is false, so exit the loop.
Line 16
1return indexOfMaximumInRange(A, 2, 3)Inside the helper:
1best = 2The loop compares index 3 with the current best:
1A[3] > A[2]
29 > 7Update:
1best = 3Return:
13The method returns index 3, whose value is 9.
Assume A is nonempty and strictly unimodal: it strictly increases to one unique maximum and strictly decreases afterward.
We show that peakIndexStrictUnimodal returns the index of that maximum.
Before the loop:
1low = 0
2high = length(A) - 1The interval [low, high] contains every array index. Therefore, it contains the unique maximum.
The invariant holds before the first reduction step.
Assume the invariant holds at the start of an iteration: the unique maximum lies in [low, high].
The loop runs only when the interval has more than two elements, so m1 < m2.
A[m1] < A[m2]Suppose the maximum were at m1 or to the left of it. Then the array would be strictly decreasing from m1 through m2, which would give:
1A[m1] > A[m2]That result conflicts with the comparison result.
The maximum is strictly right of m1. Updating:
1low = m1 + 1removes no possible maximum. The new interval still contains the unique maximum.
A[m1] > A[m2]Suppose the maximum were at m2 or to the right of it. Then the array would be strictly increasing from m1 through m2, which would give:
1A[m1] < A[m2]That result conflicts with the comparison result.
The maximum is strictly left of m2. Updating:
1high = m2 - 1removes no possible maximum. The new interval still contains the unique maximum.
Every reduction preserves the invariant.
Each iteration discards at least one portion of the interval. Eventually, the candidate interval has one or two indices, and the loop stops.
By the invariant, the unique maximum is among those remaining indices. indexOfMaximumInRange compares every value in that final interval and returns an index holding its largest value.
Therefore, it returns the index of the unique maximum of the original array.
Let m be the current candidate interval length.
1m = high - low + 1Each reduction computes two indices and performs one value comparison.
After the comparison, the retained interval is at most roughly two thirds of the previous interval, with a constant rounding effect from integer division.
After k reductions, the remaining length is approximately:
The loop stops when the interval reaches a fixed size of at most 2. So we need:
to become constant-sized.
That requires k proportional to:
So the number of loop iterations is:
The final direct scan examines at most two values because the threshold is fixed. Its work is O(1) relative to n.
Therefore:
O(log n)O(1)The method is iterative. It stores only a fixed number of indices and variables: low, high, m1, m2, and the helper’s best.
Incorrect assumption: Every array has one rising side and one falling side.
Exposing input:
1index: 0 1 2 3 4
2A: 1 9 2 8 3The array has multiple peaks: 9 at index 1 and 8 at index 3.
A comparison-based discard can remove the part containing the global maximum because the strict-unimodal proof no longer applies.
Correction: Require a strictly unimodal input.
low = m2 after A[m1] < A[m2]Incorrect line:
1low = m2Exposing input:
1A = [1, 4, 7, 9, 6, 2]At the first state:
1m1 = 1, A[m1] = 4
2m2 = 4, A[m2] = 6Since 4 < 6, the correct retained interval is:
1[m1 + 1, high] = [2, 5]If the code sets:
1low = m2 = 4it discards indices 2 and 3. Index 3 is the actual peak.
Correction:
1low = m1 + 1Incorrect assumption:
1A[m1] == A[m2] means the maximum is between themExposing input:
1A = [1, 3, 3, 2]The equal values 3 and 3 form a plateau. There is no unique strict maximum.
Correction: Reject such input or define a separate plateau policy. The method requires strict unimodality.
Incorrect approach:
1compare A[m1] and A[m2]
2return the index with the larger valueExposing input:
1A = [1, 4, 7, 9, 6, 2]At the first state:
1m1 = 1, A[m1] = 4
2m2 = 4, A[m2] = 6The approach returns index 4, because 6 > 4.
The actual maximum is:
1index 3, value 9The split values identify a region that can be discarded. They do not always identify the peak.
Correction: Continue reducing the candidate interval, then scan the fixed-size final interval.
| Input | Expected returned index | Reason |
|---|---|---|
[5] | 0 | The only element is the maximum. |
[1, 3] | 1 | The final scan selects 3. |
[3, 1] | 0 | The final scan selects 3. |
[1, 4, 7, 9, 6, 2] | 3 | The worked example. |
[1, 2, 3, 2, 1] | 2 | The central value is the unique peak. |
[1, 3, 3, 2] | not covered | The plateau violates strict unimodality. |
Implement:
1peakIndexStrictUnimodal(A)Contract to test:
A.No mapped executable problem is supplied for this lesson.
1def peak_index(a):
2 low, high = 0, len(a) - 1
3 while high - low + 1 > 2:
4 m1 = low + (high - low) // 3
5 m2 = high - (high - low) // 3
6 if a[m1] < a[m2]:
7 low = m1 + 1 # peak is right of m1
8 elif a[m1] > a[m2]:
9 high = m2 - 1 # peak is left of m2
10 else:
11 raise ValueError("not strictly unimodal")
12 best = low # scan the last one or two indices
13 for i in range(low + 1, high + 1):
14 if a[i] > a[best]:
15 best = i
16 return best
17
18print(peak_index([1, 4, 7, 9, 6, 2]))
19print(peak_index([3, 1]))
20print(peak_index([1, 3]))
21print(peak_index([5]))1public class Main {
2 static int peakIndex(int[] a) {
3 int low = 0, high = a.length - 1;
4 while (high - low + 1 > 2) {
5 int m1 = low + (high - low) / 3;
6 int m2 = high - (high - low) / 3;
7 if (a[m1] < a[m2]) low = m1 + 1; // peak is right of m1
8 else if (a[m1] > a[m2]) high = m2 - 1; // peak is left of m2
9 else throw new IllegalArgumentException("not strictly unimodal");
10 }
11 int best = low; // scan the last one or two indices
12 for (int i = low + 1; i <= high; i++) {
13 if (a[i] > a[best]) best = i;
14 }
15 return best;
16 }
17
18 public static void main(String[] args) {
19 System.out.println(peakIndex(new int[]{1, 4, 7, 9, 6, 2}));
20 System.out.println(peakIndex(new int[]{3, 1}));
21 System.out.println(peakIndex(new int[]{1, 3}));
22 System.out.println(peakIndex(new int[]{5}));
23 }
24}1#include <iostream>
2#include <stdexcept>
3#include <vector>
4using namespace std;
5
6int peakIndex(const vector<int>& a) {
7 int low = 0, high = (int)a.size() - 1;
8 while (high - low + 1 > 2) {
9 int m1 = low + (high - low) / 3;
10 int m2 = high - (high - low) / 3;
11 if (a[m1] < a[m2]) low = m1 + 1; // peak is right of m1
12 else if (a[m1] > a[m2]) high = m2 - 1; // peak is left of m2
13 else throw invalid_argument("not strictly unimodal");
14 }
15 int best = low; // scan the last one or two indices
16 for (int i = low + 1; i <= high; i++) {
17 if (a[i] > a[best]) best = i;
18 }
19 return best;
20}
21
22int main() {
23 cout << peakIndex({1, 4, 7, 9, 6, 2}) << endl;
24 cout << peakIndex({3, 1}) << endl;
25 cout << peakIndex({1, 3}) << endl;
26 cout << peakIndex({5}) << endl;
27}1function peakIndex(a) {
2 let low = 0, high = a.length - 1;
3 while (high - low + 1 > 2) {
4 const m1 = low + Math.floor((high - low) / 3);
5 const m2 = high - Math.floor((high - low) / 3);
6 if (a[m1] < a[m2]) low = m1 + 1; // peak is right of m1
7 else if (a[m1] > a[m2]) high = m2 - 1; // peak is left of m2
8 else throw new Error('not strictly unimodal');
9 }
10 let best = low; // scan the last one or two indices
11 for (let i = low + 1; i <= high; i++) {
12 if (a[i] > a[best]) best = i;
13 }
14 return best;
15}
16
17console.log(peakIndex([1, 4, 7, 9, 6, 2]));
18console.log(peakIndex([3, 1]));
19console.log(peakIndex([1, 3]));
20console.log(peakIndex([5]));Finding the peak of a strictly unimodal sequence, such as [1, 4, 7, 9, 6, 2], where the maximum sits at index 3. Flipping both comparisons finds the minimum of a sequence that falls and then rises.
No. Each ternary step keeps about two thirds of the interval, while binary search keeps half, so ternary needs more steps: log base 3/2 of n against log base 2. Use binary search for sorted lookups and ternary search for a single peak.
A separate data structure, a trie-like tree used for strings. It has no connection to the ternary search algorithm described here.
If A[m1] equals A[m2], the input has a flat top such as [1, 3, 3, 2], and the proof no longer applies. The method needs strict increase then strict decrease. Reject such input or define a plateau rule.
The peak can lie between m1 and m2. In [1, 4, 7, 9, 6, 2], m1 = 1 and m2 = 4, and low = m2 would drop index 3, the peak.