Skip to main content

Search in Rotated Sorted Array

Learn Search in Rotated Sorted Array (Searching, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Binary Search on a Rotated Array A sorted array rotated at some unknown pivot (e.g. [4,5,6,7,0,1,2] ) is no longer fully sorted, but at every step, AT LEAST ONE HALF around the midpoint IS sorted. Determine which half is sorted, check if the target lies within that sorted half's range, and recurse into the correct side - still O(log n).

More lessons in Searching