HHot 100C++ 图解

33. 搜索旋转排序数组

中等 二分查找 4 帧动画 在力扣上做

一句话套路先判断哪一半有序,再决定往哪收缩

题目描述

整数数组 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
输出:4

示例 2:

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

示例 3:

输入:nums = [1], target = 0
输出:-1

 

提示:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

思路

时间O(log n)
空间O(1)

核心判断

mid 把数组分成两半,「至少有一半是有序的」。

  • · nums[lo] <= nums[mid] -> 左半有序:target 落在 [nums[lo], nums[mid]) 就去左边,否则右边。

· 否则右半有序

target 落在 (nums[mid], nums[hi]] 就去右边,否则左边。

用 nums[lo] <= nums[mid] 而不是 < ,是为了处理 lo == mid(区间长度 2)。

陷阱

本题元素互不相同;若有重复就退化成 Q81,需要 nums[lo]==nums[mid] 时 lo++ 慢慢缩。

图解

4 0 5 1 6 2 7 3 0 4 1 5 2 6
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/11_binary_search.cpp24 行
namespace lc0033 {
class Solution {
 public:
  int search(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      if (nums[mid] == target) return mid;
      if (nums[lo] <= nums[mid]) {  // 左半 [lo, mid] 有序
        if (nums[lo] <= target && target < nums[mid])
          hi = mid - 1;
        else
          lo = mid + 1;
      } else {                      // 右半 [mid, hi] 有序
        if (nums[mid] < target && target <= nums[hi])
          lo = mid + 1;
        else
          hi = mid - 1;
      }
    }
    return -1;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q33_search_rotated14 行
lc0033::Solution s;
vector<int> a{4, 5, 6, 7, 0, 1, 2};
CHECK_EQ(s.search(a, 0), 4);
CHECK_EQ(s.search(a, 4), 0);
CHECK_EQ(s.search(a, 3), -1);
CHECK_EQ(s.search(a, 2), 6);   // 最小值在末尾附近
CHECK_EQ(s.search(a, 7), 3);   // 最大值
vector<int> b{1};
CHECK_EQ(s.search(b, 0), -1);
vector<int> c{3, 1};
CHECK_EQ(s.search(c, 1), 1);   // 两元素旋转,考验 lo==mid
CHECK_EQ(s.search(c, 3), 0);
vector<int> d{1, 2, 3, 4, 5};  // 没旋转
CHECK_EQ(s.search(d, 5), 4);

↑↓ 选择↵ 打开/ 随时唤起