V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Ternary Search

Compare two interior probes and discard one third of a unimodal search interval each round.

Core idea

For a unimodal objective, compare points at one third and two thirds of the interval. Their values identify one outer third that cannot contain the peak.

Read the visualization

The plotted curve keeps both probes and shades the discarded third. Repeated probes close around the unique maximum until the chosen precision is reached.

1
4
7
9
12
10
6
3
2

Begin with an interval known to contain one peak of a unimodal objective.

1function ternaryPeak(a: number[]): number {
2 let lo = 0, hi = a.length - 1; // unimodal array
3 while (lo < hi) {
4 const third = ((hi - lo) / 3) | 0;
5 const m1 = lo + third, m2 = hi - third; // probe count probe
6 if (a[m1] < a[m2]) lo = m1 + 1; // probe not probe m1 left side: probe left 1/3
7 else hi = m2 - 1; // probe not probe m2 right side: probe right 1/3
8 }
9 return lo; // peak top
10}
11// done degree done: compare a[mid] and a[mid+1], up done right, down done left
shapeunimodal ( ascending then descending)
[lo, hi][0, 8]
m1 / m2— / —
candidate number9
1 / 7

Complexity and tradeoffs

Time: O(log range). Space: O(1). The objective must be unimodal; continuous search stops at a chosen precision.

Invariant: The remaining interval always contains a global peak of the unimodal objective.

Where it fits

Ternary search optimizes unimodal discrete or continuous functions when derivatives are unavailable. Convex minimization uses the symmetric comparison direction.