LeetCode33.搜索旋转排序数组

题目概述

链接：点我做题

题解 一、找到翻转的点

  因为翻转后两边都是部分有序的，都是满足前一个元素比后一个元素小的，当出现前一个元素比后一个元素大的时候说明出现了翻转点，我们知道这个反转的结果是把原本一团小的有序的数组放到了后面，因此找到反转点后，这个翻转点的元素就是有序数组中最大的元素，如果目标元素比它大，就可以直接返回-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)