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

Binary Search on the Answer

Turn an optimization problem into a monotone feasibility predicate and search the numeric answer range.

Core idea

Replace direct optimization with a yes-or-no predicate such as whether capacity x is sufficient. If feasibility changes only once, binary search finds that boundary.

Read the visualization

The numeric answer interval shrinks around each midpoint. The feasibility panel explains the check, and colors distinguish impossible from feasible values.

1
2
3
4
5
6
7
8
9
10
11

Define the numeric answer interval and its monotone feasibility predicate.

1function minEatingSpeed(piles: number[], h: number): number {
2 let lo = 1, hi = Math.max(...piles); // answer empty between [1, max]
3 while (lo < hi) {
4 const mid = (lo + hi) >> 1; // probe one answer
5 if (canFinish(piles, mid, h)) hi = mid; // feasible: answer probe
6 else lo = mid + 1; // not feasible: probe
7 }
8 return lo; // minimum feasible speed
9}
10// canFinish(k): Σ ceil(pile / k) <= h —— k done feasible (done word)
banana piles[3, 6, 7, 11]
time limit h8 when smaller
candidate speed [lo, hi][1, 11]
mid—
1 / 7

Complexity and tradeoffs

Time: O(check × log range). Space: O(1) beyond the check. Correctness depends on a monotone predicate and a precisely defined first-true or last-true boundary.

Invariant: All values strictly below the lower boundary are known impossible, while the retained interval still contains the first feasible answer.

Where it fits

Binary search on the answer solves capacity planning, partition limits, minimum speed, maximum spacing, and many problems whose candidate range is ordered but not explicitly listed.