【leetcode】33. 搜索旋转排序数组

题目内容

33. 搜索旋转排序数组

思路分析

本题是一道二分查找的进阶题目。

参考资料：官方题解

方法一：二分查找

图源leetcode

做这道题目需要意识到一个性质：在搜索范围是旋转排序数组的情况下，二分的结果是左右两半有一半是有序的，有一半是乱序的。

而判断哪一部分乱序的方法为判断nums[0]和nums[mid]的大小：

若nums[0] > nums[mid]，则左半部分乱序
若nums[0] < nums[mid]，则右半部分乱序

通过这一性质，我们可以通过以下流程进行二分：

判断乱序是哪一部分
判断要查找的数target是否在顺序部分的范围内
- 如果在，则正常对顺序部分进行二分
- 如果不在，则将搜索范围变为乱序部分，继续进行1、2两步

使用这样的方法，我们即可在旋转数组上进行二分搜索。

在代码实现时有些细节需要注意：

要意识到这点：一旦开始对顺序部分进行搜索，则以后要接触到的都是顺序部分。而接触到顺序部分之前之后的代码是可以复用的。可对比自己实现版和答案改进版的区别。
在对数组进行操作时，尽量避免使用nums[mid+1]或nums[mid-1]，否则很容易造成数组越界。

代码

#include <vector>
#include <math.h>
#include <limits.h>

using namespace std;

// 二分查找--自己写的版
// 时间复杂度O(logn)
// 空间复杂度O(1)
class Solution {
public:
    int search(vector<int>& nums, int target) {
       int left = 0, right = nums.size() - 1;
       bool order = false; // 标记处理的数组是否有序
       while (left <= right) {
          int mid = left + (right - left) / 2;

          if (nums[mid] == target) {
             return mid;
          // 若此时处理的数组无序，则需要判断哪边是有序的
          } else if (!order){
               // 左边乱序，右边顺序
               if (nums[0] > nums[mid]) {
                  // target在右边范围内
                  // 注意到这里用的是target>nums[mid]而不是target>=nums[mid+1]
                  // 避免了mid+1越界的问题，下同
                  if (target > nums[mid] && target <= nums[right]) {
                     left = mid + 1;
                     order = true;
                  // target在左边范围内
                  } else {
                     right = mid - 1;
                  }
               // 左边顺序，右边乱序
               } else {
                  // target在左边范围内
                  if (target >= nums[left] && target < nums[mid]) {
                     right = mid - 1;
                     order = true;
                  // target在左边范围内
                  } else {
                     left = mid + 1;
                  }
               }
          // 若此时处理的数组有序，则正常进行二分查找
          } else {
             if (nums[mid] > target) {
                right = mid - 1;
             } else {
                left = mid + 1;
             }
          }
        }
        return -1;
    }
};

// 二分查找--看了答案后的修改版
// 时间复杂度O(logn)
// 空间复杂度O(1)
class Solution {
public:
    int search(vector<int>& nums, int target) {
       int left = 0, right = nums.size() - 1;
       
       while (left <= right) {
          int mid = left + (right - left) / 2;

          if (nums[mid] == target) {
             return mid;
          // 若此时处理的数组无序，则需要判断哪边是有序的
          // 左边乱序，右边顺序
          } else if (nums[0] > nums[mid]) {
               // target在右边范围内
               // 注意到这里用的是target>nums[mid]而不是target>=nums[mid+1]
               // 避免了mid+1越界的问题，下同
               if (target > nums[mid] && target <= nums[right]) {
                  left = mid + 1;
               // target在左边范围内
               } else {
                  right = mid - 1;
               }
            // 左边顺序，右边乱序
          } else {
               // target在左边范围内
               if (target >= nums[left] && target < nums[mid]) {
                  right = mid - 1;
               // target在左边范围内
               } else {
                  left = mid + 1;
               }
          }
        }
        return -1;
    }
};

int main() {
   Solution s;
   vector<int> input{ 1,3 };
   int target = 0;
   int result = s.search(input, target);
   int a = 0;
}

收获

再次巩固了下二分，二分比排序简单多了