LeetCode Q33: Search in Rotated Sorted Array (hard)

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

The question looks very easy at the first glance, since we could easily restore the sorted array first followed by a binary search. However, to restore the array may either need extra space or O(n) to rearrange the elements in the array.

I guess the reason leetcode put a "hard" label for this question is because it is requested to be solved in O(logn) time and in space, which comes  a solution using binary search:

To use a binary search on a rotated array, we should understand when to get rid off half of the elements and which half to remove. Let's take removal of the left half for example, there are three cases in total:

case 1 --- (target)7 in:     (left)2, 3, 4, 5, (mid)6, 7, 0, (right)1

case 2 --- (target)0 in:     (left)2, 3, 4, 5, (mid)6, 7, 0, (right)1

case 3 --- (target)4 in:     (left)6, 7, 0, 1, (mid)2, 3, 4, (right)5

For case 1:  nums[mid]>=nums[left] && target>nums[mid]

For case 2:  nums[mid]>=nums[left] && target

For case 3:  nums[mid]nums[mid] && target<=nums[right]

That's all cases we have to get rid of the elements in the left half of the array and move left pointer to mid+1. For all other cases, we just move right pointer to mid-1.

So comes the following code:

This code runs 4ms for all test cases.

For curiosity, I also tried a linear search solution, with surprise to see it can also finish search in 4ms. Simple method works in this case.

Solution: Second round
Second round solution 2:
For such question, rememeber to use nums[mid] to compare with either nums[left] or nums[right] first, this will separate cases really fast.