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

Search in a Rotated Sorted Array

Identify the sorted half at each binary-search probe and keep the half that can contain the target.

Core idea

A rotated sorted array still has at least one sorted half around every midpoint. Determine that half, test whether the target falls inside its value range, and discard the other half.

Read the visualization

Low, midpoint, and high pointers bound the candidate interval. Each step labels the sorted half and visibly removes the half that cannot contain the target.

13
15
17
1
3
5
7
9
11

Begin with the entire rotated sorted array as the candidate interval.

1function searchRotated(a: number[], t: number): number {
2 let lo = 0, hi = a.length - 1;
3 while (lo <= hi) {
4 const mid = (lo + hi) >> 1;
5 if (a[mid] === t) return mid; // hit
6 if (a[lo] <= a[mid]) { // left half sorted
7 if (a[lo] <= t && t < a[mid]) hi = mid - 1; // probe ordered left half
8 else lo = mid + 1; // probe right half
9 } else { // right half sorted
10 if (a[mid] < t && t <= a[hi]) lo = mid + 1; // probe ordered right half
11 else hi = mid - 1; // done left half
12 }
13 }
14 return -1;
15}
break point17 ↘ 1(idx 2/3 between)
target5
[lo, hi][0, 8]
mid—
choose a half—
1 / 8

Complexity and tradeoffs

Time: O(log n). Space: O(1). The logarithmic guarantee assumes distinct values; duplicates can obscure which half is sorted.

Invariant: The target, when present, remains inside the current inclusive candidate interval after every half elimination.

Where it fits

This pattern handles searches across one unknown cyclic pivot. Repeated values may make both halves ambiguous and can degrade the worst case to linear time.