sorted ↑
sorted ↑ (smaller)
4
5
6
7
0
1
2
[0][1][2][3][4][5][6]
Brute force · linear scan
▸1given arr, target2for i ← 0 to n − 1:3 if arr[i] == target: return i4return −1
state
- target0
warming up the animation
Given an ascending sorted array that has been rotated at an unknown pivot, find the index of a target value in O(log n) time, returning -1 if it is not present.
▸1given arr, target2for i ← 0 to n − 1:3 if arr[i] == target: return i4return −1
line 1A sorted array was ROTATED: [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2]. Find 0. The cliff (7 → 0) seems to break binary search, so first instinct: linear scan.