二分与排序中等1 种解法

#33搜索旋转排序数组

在无重复值的旋转升序数组中以 O(log n) 时间查找目标下标。

#数组#二分查找

解题主线

每轮至少有一半区间保持有序；判断 target 是否落在该有序闭区间即可排除另一半。

解法 1：识别有序半区的二分

比较 nums[left] 与 nums[middle] 识别有序侧，再判断目标是否位于该侧。

时间复杂度

O(log n)

空间复杂度

O(1)

33. 搜索旋转排序数组 · 识别有序半区的二分

java

final class Solution {
    public int search(int[] nums, int target) {
        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;
    }
}

比较 nums[left] 与 nums[middle] 识别有序侧，再判断目标是否位于该侧。

边界与易错点

本题无重复元素；存在重复值时无法总是根据边界判断哪侧有序。
区间端点的等号必须与被保留的闭区间一致。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

medium/Q033_searchRotateSortedArr.java