leetcode：33. 搜索旋转排序数组

题目

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标（旋转后数组中的下标），否则返回 -1 。

进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？

示例：

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

解答 & 代码

二分查找，使用 mid 将数组分为左右两部分，至少有一个部分是有序的，根据有序的半边来判断将搜索范围缩小到左半边还是右半边
image.png

  1. class Solution {     
  2. public:
  3.     int search(vector<int>& nums, int target) {
  4.         int left = 0;
  5.         int right = nums.size() - 1;
  6.         while(left <= right)
  7.         {
  8.             int mid = left + (right - left) / 2;
  9.             // 若找到，则直接返回
  10.             if(nums[mid] == target)
  11.                 return mid;
  12.             // 若左半边 [left, mid] 有序
  13.             // 注意等号，特殊情况 left==right 时, mid 和 left 是一个数，也算左半边有序            
  14.             else if(nums[left] <= nums[mid])    
  15.             {
  16.                 // 如果 target 在左半边，则搜索范围收缩到左半边
  17.                 if(target >= nums[left] && target < nums[mid])
  18.                     right = mid - 1;
  19.                 // 否则 target 在右半边，则搜索范围收缩到右半边
  20.                 else
  21.                     left = mid + 1;
  22.             }
  23.             // 若右半边 [mid, right] 有序
  24.             else
  25.             {
  26.                 // 如果 target 在右半边，则搜索范围收缩到右半边
  27.                 if(target > nums[mid] && target <= nums[right])
  28.                     left = mid + 1;
  29.                 // 否则 target 在左半边，则搜索范围收缩到左半边
  30.                 else
  31.                     right = mid - 1;
  32.             }
  33.         }
  34.         return -1;    // 未找到，返回 -1
  35.     }
  36. };

复杂度分析：设数组 nums 长为 N

  • 时间复杂度 O(logN)
  • 空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 71.53% 的用户
  4. 内存消耗：10.9 MB, 在所有 C++ 提交中击败了 13.58% 的用户