LeetCode0033-搜索旋转排序数组

发表于 | 分类于 ，

问题描述

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

示例 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. 1 <= nums.length <= 5000
  2. -10^4 <= nums[i] <= 10^4
  3. nums 中的每个值都独一无二
  4. 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  5. -10^4 <= target <= 10^4

解题思路

对于有序数组总查找某个值，常用的方法就是二分法。但是在本题中，有序数组经过“旋转”后，变成了两个有序序列，不能仅通过较中间元素和目标值的大小去决定下次二分的范围。下面就研究下，在本题的条件下，如何确定二分法后应在中间元素的哪侧进行继续查找。

假设 nums 是要查询的数组，target 为查询的目标值，令指针low 指向第一个元素，指针 high 指向最后一个元素，指针 mid 指向数组的中间元素，即 mid = (low + high) / 2。

  • 若 target == nums[mid]，则找到，直接结束查找。
  • 若 nums[low] <= nums[mid]，则 mid 左侧为有序数组（=符号是要考虑，最后只剩下两个元素或数组只有两个元素的时候），旋转点应在 mid 右侧。此时，若目标值在 low 和 mid 之间，即 num[low] <= target < nums[mid]，那么下次应在 mid 左侧查找，即查找范围变为：[low, mid -1]。否则，应在 mid 右侧查找，查找范围变为：[mid + 1, high]。
  • 若 nums[low] > nums[mid]，则旋转点在 mid 左侧，mid 右侧为有序数组，且 mid 右侧的值都比 nums[low] 小。此时，
    • 若 target > nums[low] > nums[mid]，由于 mid 右侧的数值都比 nums[low] 小，那下次查找范围应在 mid 左侧，即查找范围变为：[low, mid -1]；
    • 若 nums[low] > target > nums[mid]，此时 target 应在 mid 右侧，即查找范围变为：[mid + 1, high]；
    • 若 nums[low] > nums[mid] > target，此时 target 应在旋转点和 mid 间，查找范围变为：[low, mid -1]；
  • 重复以上步骤，直到找到 target 或指针 low 和指针 high 相遇。

代码

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
public int search(int[] nums, int target) {
    if (nums == null || nums.length < 1) {
        return -1;
    }
    if (nums.length == 1 && nums[0] != target) {
        return -1;
    }
    int index = -1;
    int low = 0;
    int high = nums.length - 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if (nums[mid] == target) {
            index = mid;
            break;
        }
        if (nums[low] <= nums[mid]) {
            if (nums[low] <= target && target < nums[mid]) {
                high = mid -1;
            } else {
                low = mid + 1;
            }
        } else {
            // nums[low] > nums[mid]
            if (nums[low] > target  && target > nums[mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

    }
    return index;
}