I submitted the solution before and I realized that my solution is not good enough as it is O(n). But the system accept it.

In my last submit, I try to find the index which the rotate happen, then use the binary search. Which will be O(n)+O(log(n) at the worst case.