当前位置：首页 > news >正文

【LeetCode 热题 100】33. 搜索旋转排序数组——（解法二）一次二分

news 2025/8/1 19:49:28

Problem: 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) 的算法解决此问题。

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(log N)
- 空间复杂度：O(1)

整体思路

这段代码同样旨在解决 “在旋转排序数组中搜索目标值” 的问题。与上一个“先找最小值，再二分”的两步法不同，此版本采用了一种更为一体化、也更具挑战性的 “单次二分查找” 策略。它通过一个精心设计的 check 函数，将复杂的判断逻辑融入到二分查找的每一步中，从而在一次循环内完成搜索。

算法的核心思想是：在二分查找的每一步，通过 nums[mid] 和数组边界值（nums[n-1]）的关系，以及 target 和边界值的关系，来确定 target 和 nums[mid] 是否在同一个单调区间内。然后根据这个关系来决定是收缩左边界还是右边界。

染色法/划分思想：
- check(nums, mid, target) 函数是算法的灵魂。我们可以将其理解为一种“染色”或“划分”的逻辑。它将整个（概念上的）循环数组划分为两部分：一部分是 check 返回 true 的区域，另一部分是 check 返回 false 的区域。
- 我们的二分查找目标就是找到这两个区域的分界线。
check 函数的逻辑详解：
- check 函数的目的是判断 nums[mid] 是否可能是我们要找的 target 或者在 target 的“右边”（在循环数组的意义上）。如果 check 返回 true，意味着最终答案在 mid 或其左侧；如果返回 false，则答案在 mid 的右侧。
- check 内部的逻辑可以这样理解：
  a. x > nums[n-1]：这个条件判断 nums[mid] 是在数组的左半部分（蓝色区域）还是右半部分（红色区域）。
  - Case 1: nums[mid] 在左半部分（蓝色）：
    * 此时，如果 target 也落在这一段（即 target > nums[n-1]），并且 target <= nums[mid]，那么 target 和 mid 在同一个单调区间内，且 target 在 mid 或其左侧。check 应返回 true。
    * 如果 target 落在右半部分（即 target <= nums[n-1]），那么 target 和 mid 不在同一个单调区间内。target 相当于在 mid 的“右边”（循环意义上），check 应返回 false。
    * return target <= x && target > nums[n-1] 这句代码巧妙地整合了这两种情况。
  - Case 2: nums[mid] 在右半部分（红色）：
    * 此时，如果 target 落在左半部分（即 target > nums[n-1]），那么 target 相当于在 mid 的“左边”（循环意义上），check 应返回 true。
    * 如果 target 也落在右半部分（即 target <= nums[n-1]），并且 target <= nums[mid]，那么它们在同一个单调区间内，target 在 mid 或其左侧，check 应返回 true。
    * return target > nums[n-1] || target <= x 这句代码也巧妙地整合了这两种情况。
二分查找框架：
- 代码使用了一个标准的 lower_bound 形式的二分查找框架 while (left < right)。
- 根据 check 函数的返回值来收缩边界：
  - check 返回 true，说明答案在 [left, mid] 区间，所以 right = mid。
  - check 返回 false，说明答案在 [mid+1, right) 区间，所以 left = mid + 1。
- 循环结束后，left 指针会停在分界点上，也就是第一个可能等于 target 的位置。
- 最后通过 nums[left] == target 确认并返回结果。

完整代码

class Solution {/*** 在一个旋转排序数组中搜索目标值（单次二分查找版）。* @param nums 旋转排序数组* @param target 要搜索的目标值* @return 目标值的索引，如果不存在则返回 -1*/public int search(int[] nums, int target) {int left = 0;int right = nums.length;if (nums.length == 0) return -1; // 边界检查，防止空数组// 这是一个 lower_bound 形式的二分查找框架while (left < right) {int mid = left + (right - left) / 2;// check 函数判断 mid 是否在 target 的“右侧”（或就是target）if (check(nums, mid, target)) {// 如果是，则答案在 [left, mid] 区间内right = mid;} else {// 如果不是，则答案在 [mid + 1, right) 区间内left = mid + 1;}}// 循环结束时，left 指向第一个可能等于 target 的位置。// 需要额外检查 left 是否越界以及该位置的值是否真的等于 target。return left < nums.length && nums[left] == target ? left : -1;}/*** 核心检查函数，用于在二分查找中确定收缩方向。* 它的逻辑是将整个循环数组根据 target 划分为两部分。* @param nums 数组* @param mid 中间点索引* @param target 目标值* @return 如果 mid 可能在答案的右半部分（包含答案本身），返回 true。*/private boolean check(int[] nums, int mid, int target) {int x = nums[mid];int n = nums.length;// Case 1: mid 落在数组的左侧有序部分 (e.g., [4,5,6,7,0,1,2], mid 在 4,5,6,7)if (x > nums[n - 1]) {// 要让 check 返回 true (即 right = mid)，target 必须也在左侧部分，且 target <= x// 也就是 nums[n-1] < target <= xreturn target <= x && target > nums[n - 1];}// Case 2: mid 落在数组的右侧有序部分 (e.g., [4,5,6,7,0,1,2], mid 在 0,1,2)// 要让 check 返回 true (即 right = mid)，target 的情况有两种：// a) target 落在左侧部分 (target > nums[n-1])，此时 mid 永远在 target 的右边（循环意义上）// b) target 也落在右侧部分，且 target <= xreturn target > nums[n - 1] || target <= x;}
}