Search in a Rotated Array ​
Search in a Rotated Array — LeetCode
Search for a target in a sorted array that has been rotated at an unknown pivot, in O(log n).
Approach ​
The idea is to figure out which part is the sorted part and whether the target is in sorted or unsorted part.
At each mid, check if left part is sorted or right part is sorted. Then in the sorted part, check if the target is between mid and the sorted part's pointer (l or r). Then decide where to move it.
Remarks ​
This problem had me screwed over comparison + equals.