LC.P33[搜索旋转排序数组]

方法一：两次二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 1) return nums[0] == target ? 0 : -1;
        int left = 0, right = n - 1;
        // 从中间开始找，找到满足 >= nums[0] 的分割点（旋转点）
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (nums[mid] >= nums[0]) left = mid;
            else right = mid - 1;
        }
        // 通过和 nums[0] 比较，确定 target 是在旋转点的左边还是右边
        if (target >= nums[0]) {
            left = 0;
        } else {
            left = left + 1;
            right = n - 1;
        }
        while (left < right) {
            int mid = left + right >> 1;
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        return nums[right] == target ? right : -1;
    }
}
  • 时间复杂度：$O(logn)$
  • 空间复杂度：$O(1)$

方法二：遍历+二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length, idx = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                idx = i;
                break;
            }
        }
        int ans = binarySearch(nums, 0, idx, target);
        if (ans != -1) return ans;
        if (idx + 1 < n) ans = binarySearch(nums, idx + 1, n - 1, target);
        return ans;
    }

    private int binarySearch(int[] nums, int left, int right, int target) {
        while (left < right) {
            int mid = left + right >> 1;
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        return nums[left] == target ? left : -1;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$