链接：点我做题
因为翻转后两边都是部分有序的，都是满足前一个元素比后一个元素小的，当出现前一个元素比后一个元素大的时候说明出现了翻转点，我们知道这个反转的结果是把原本一团小的有序的数组放到了后面，因此找到反转点后，这个翻转点的元素就是有序数组中最大的元素，如果目标元素比它大，就可以直接返回-1了，否则比较一下这个元素和前面这个有序数组中最小的元素的大小，如果比前面这个有序数组中最小的元素小，就二分查找前面这个有序数组，如果比前面这个有序数组大，就二分查找反转点后的那个本来在“前面的”的小的有序数组。
class Solution {
public:
int search(vector& nums, int target)
{
int n = nums.size();
if (n == 1)
{
return target == nums[0] ? 0 : -1;
}
int prev = nums[0];
int right = n - 1;
for (int i = 1; i < n; ++i)
{
if (prev > nums[i])
{
right = i - 1;
break;
}
prev = nums[i];
}
int left = 0;
if (target > nums[right])
{
return -1;
}
if (target >= nums[left])
{
return binarysearch(nums, left, right, target);
}
else
{
return binarysearch(nums, right + 1, n - 1, target);
}
}
int binarysearch(vector& nums, int left, int right, int target)
{
if (left > right)
{
return -1;
}
if (target < nums[left] || target > nums[right])
{
return -1;
}
while (left <= right)
{
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
{
return mid;
}
else if (nums[mid] > target)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return -1;
}
};
时间复杂度:
O
(
N
)
O(N)
O(N)
空间复杂度:
O
(
1
)
O(1)
O(1)
观察到一个性质：设区间左端点是left,区间右端点是right,则令区间中点mid = (left+ right) / 2,
如果区间的中点的值大于区间右端点的值，则说明翻转点在(mid, right),这也说明了左区间是有序的，就可以对先检查一下目标值是否在左区间范围内，如果不在则丢弃左区间，否则对左区间进行二分查找；
如果区间中点的值小于区间右端点的值，那么说明翻转点在(left, mid),右区间有序，同理，可以先检查一下目标值是否在右区间范围内，如果不在则丢弃右区间，否则对右区间进行二分查找。
这个解法基于存在反转点的区间总是部分有序的，可以一直这样划分下去，也是每次舍弃一半区间，其实也是一种二分查找。
class Solution {
public:
int search(vector& nums, int target)
{
int left = 0, right = nums.size() - 1;
while (left <= right)
{
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
{
return mid;
}
else if (nums[mid] < nums[right])
{
if (target > nums[mid] && target <= nums[right])
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
else
{
if (target >= nums[left] && target < nums[mid])
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
}
return -1;
}
};
时间复杂度：
O
(
l
o
g
n
)
O(logn)
O(logn)
空间复杂度：
O
(
1
)
O(1)
O(1)
