题目

升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

示例1

  1. 输入：nums = [4,5,6,7,0,1,2], target = 0
  2. 输出：4

示例2

  1. 输入：nums = [4,5,6,7,0,1,2], target = 3
  2. 输出：-1

实现

思路1 暴力搜索

直接线性搜索target。
时间复杂度：33. 搜索旋转排序数组 - 图1
空间复杂度：33. 搜索旋转排序数组 - 图2
**

思路2 二分查找

题目强调数组是排序的，所以其实是在暗示使用二分查找的方法。
虽然该题的数组经过“旋转”，但将数组从中间分开两部分时，一定有一部分的数组是有序的，所以依然可以基于二分查找的思路去解决该题。
以示例1的[4,5,6,7,0,1,2]为例，

  1. 先求得mid=7，并将数组分为[4,5,6]和[7,0,1,2]两部分
  2. 然后我们判断两个部分哪边是有序的。判断方法为看子数组的左端点是否小于右端点。
    1. 若[l, mid-1]是有序数组，且target的大小在[nums[l], nums[mid]]间，那么下一步就在[l,mid]搜索；否则在[mid+1, r]中搜索；
    2. 如果[mid, r]是有序数组，且target的大小在[nums[mid], nums[r]]间，那么下一步就在[mid+1, r]搜索，否则在 [l, mid-1]中搜索。

代码实现的难点在于很多边界条件需要斟酌，例如：
判断左边数组是否有序的条件是nums[l]<=nums[mid]，一开始我把判断条件写为nums[l]<nums[mid]，结果样例nums = [3,1]， target=1出错了。因为按我的方法，判断左边数组是否有序为3<3，为false，因此程序认为右半部分为有序的，进而比较target是否在[nums[mid], nums[r]]之间，结果也为false，因此变成在[l, mid-1]即[3]中搜索，最终返回-1.

  1. class Solution {
  2. public:
  3.     int search(vector<int>& nums, int target) {
  4.         int n = nums.size();
  5.         if (n == 0) return -1;
  7.         int l=0, r=n-1;
  8.         while(l<=r) {
  9.             int mid = (l+r)/2;
  10.             if (nums[mid] == target) {
  11.                 return mid;
  12.             }
  13.             // 如果左半部分是有序的
  14.             if (nums[l]<=nums[mid]) { 
  15.                 // 如果目标在左半部分
  16.                 if (target < nums[mid] && target >= nums[l]) {
  17.                     r = mid-1;
  18.                 } else {
  19.                     l = mid+1;
  20.                 }
  21.             } else {
  22.                 if (target > nums[mid] && target <= nums[r]) {
  23.                     l = mid+1;
  24.                 } else {
  25.                     r = mid-1;
  26.                 }
  27.             }
  28.         } 
  29.         // 执行到这说明没有找到
  30.         return -1;
  31.     }
  32. };

时间复杂度：33. 搜索旋转排序数组 - 图3，其中n为数组大小。
空间复杂度：33. 搜索旋转排序数组 - 图4。