二分与排序中等1 种解法
#33搜索旋转排序数组
在无重复值的旋转升序数组中以 O(log n) 时间查找目标下标。
#数组#二分查找
原题
整数数组 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] <= 104nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转 -104 <= target <= 104
解题主线
- 每轮至少有一半区间保持有序；判断 target 是否落在该有序闭区间即可排除另一半。
解法 1：识别有序半区的二分
比较 nums[left] 与 nums[middle] 识别有序侧，再判断目标是否位于该侧。
-
时间复杂度： O(log n)
-
空间复杂度： O(1)
final class Solution {
public int search(int[] nums, int target) {
// 搜索区间保持为闭区间 [left, right]，因此循环条件需要包含等号。
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
if (nums[middle] == target) return middle;
// 无重复元素时，旋转数组的左右半区至少有一侧保持有序。
if (nums[left] <= nums[middle]) {
// 目标落在左侧有序闭区间时保留左半，否则排除左半。
if (nums[left] <= target && target < nums[middle]) right = middle - 1;
else left = middle + 1;
} else {
if (nums[middle] < target && target <= nums[right]) left = middle + 1;
else right = middle - 1;
}
}
return -1;
}
}边界与易错点
- 本题无重复元素；存在重复值时无法总是根据边界判断哪侧有序。
- 区间端点的等号必须与被保留的闭区间一致。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q033_searchRotateSortedArr.java