搜索旋转排序数组

整数数组 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：

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

示例 2：

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

二分

二分分拆分后，[left, mid] 和 [mid, right] 必有一段是有序的

  1. 算 mid：mid = left + (right-left)/2（防溢出）

  2. 如果 nums[mid]==target，直接 return mid，结束

  3. 判断左半边 

    1
    [left, mid]

    是否有序：

    1
    nums[left] <= nums[mid]

    • 左半边有序：

      • 如果 target 在左有序区间内：nums[left] ≤ target < nums[mid] → 去左边搜：right = mid -1
      • 否则 target 不在左段 → 去右边搜：left = mid +1

    • 左半边无序 ：

      右半边 [mid, right] 一定有序

      • 如果 target 在右有序区间内：nums[mid] < target ≤ nums[right] → 去右边搜：left = mid +1
      • 否则 target 不在右段 → 去左边搜：right = mid -1

  4. 循环结束，没找到 → return -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
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 找到目标
            if (nums[mid] == target) {
                return mid;
            }

            // 左段有序
            if (nums[left] <= nums[mid]) {
                // target在左段
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // 右段有序
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        // 没找到
        return -1;
    }
}