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

Searching a sorted array by discarding half at every probe

The optimal guessing strategy

In a sorted array, comparing the target with the middle value tells us which half cannot contain the answer. Binary Search keeps a closed candidate range [lo, hi], probes mid, and removes one impossible half while preserving the other.

Two complete outcomes

The player first finds 17, then searches for the absent value 4. Bright bars remain candidates; dimmed bars have already been ruled out. The second run ends with lo > hi, which is a proof that no candidate remains, not a signal to scan again.

1
3
5
7
9
11
13
15
17
19

Search for target 17 in the sorted array; start with range [0, 9].

1function binarySearch(a: number[], t: number): number {
2 let lo = 0, hi = a.length - 1; // candidate range [lo, hi]
3 while (lo <= hi) {
4 const mid = (lo + hi) >> 1; // probe the midpoint
5 if (a[mid] === t) return mid; // match found
6 if (a[mid] < t) lo = mid + 1; // target is right: discard the left half
7 else hi = mid - 1; // target is left: discard the right half
8 }
9 return -1; // empty range: not found
10}
n10
target17
[lo, hi][0, 9]
mid—
1 / 16

Invariant and cost

Precondition: the array is sorted.
Invariant: if the target exists, it remains inside [lo, hi].
Safe midpoint: use lo + ((hi - lo) >> 1) when integer overflow matters.
Cost: the range halves each time, so lookup takes O(log n) comparisons.

The same invariant-driven template powers lower bounds, upper bounds, rotated-array search, and binary search over an answer space. The important skill is defining exactly what the candidate interval means before writing the loop.