Algorithms and Data Structures · Middle · Question 16 of 75
How do you find a value in a sorted array that was rotated, like [4, 5, 6, 1, 2, 3], in O(log n)?
- 1Linear search, because the rotation breaks the order
- ✓Correct answer: Binary search, checking which half is sorted at each step
- 3Sort the array first, then run normal binary search
Explanation
Compare arr[lo] with arr[mid] to see which half is in order, then check whether the target falls into that half's range. Sorting first costs O(n log n), linear search O(n).