Search in Rotated Sorted Array

Problem

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.

---

Ideas

• http://www.cnblogs.com/TenosDoIt/p/3465240.html

这个思路关注于搜索rotated的subarray. 思路是使用二分查找：在常规情况下，当target > A[mid]时， 应该开始查找数组的后半段，即left = mid+1; 当target < A[mid]时，应该查找数组的前半段，即right = mid-1; 而此题中，当target > A[mid]时，也可能搜索数组的前半段，如：7 8 1 2 3 4 5 （target：8）当target < A[mid]时，也可能搜索数组的后半段，如： 4 5 6 7 8 1 2 （target:2)。下面来分类讨论这两种特殊情况出现的条件。 这两种情况中target都在rotated的数组中。

• target < A[mid]时，搜索后半段必须同时满足以下条件
• A[left] > A[right]          // 表明搜索的边界落在rotated subarray
• target <= A[right]          // target 可能在unrotated的数组的前半部分
• A[right] < A[mid]          // A[mid]在unrotated数组的后半部分,换言之,rotate的点靠近left
我们可以根据上述条件还原rotated前的数组 ... target... A[right].... Middle.... A[mid], 仔细看其实条件就是 A[left] > A[right] (rotated) && target <= A[right] < A[mid]
• target > A[mid]时，搜索前半段
• A[left] > A[right]          // 表明搜索的边界落在rotated subarray
• target > A[right]          // 表明target在unrotated数组的后半部分
• A[mid] < A[right]          // 表明A[mid]在unrotated数组的前半部分，换言之，rotate的点靠近right
unrotated的数组应该是 ... A[mid].... Middle....A[right]....target.....

---

Solution

Another easy idea to understand. This method only focus on searching the unsorted subarray.

---

Special Cases

---