LeetCode HOT 100 —— 33.搜索旋转排序数组

题目

整数数组 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) 的算法解决此问题。

思路

有序数组，立即推！—>二分查找，本题就是以二分搜索为基础

我第一次看完题目是懵逼的，我就想这题目想表达什么，在数组里搜索有没有这个数？

后来才明白，实际上就是给你一个旋转后的数组，让你实现一个时间复杂度为（log n）级别的搜索算法，能够在旋转后的数组上用二分法查找目标元素，即如何在非有序的数组中使用二分查找？

本题给出的nums数组是经过旋转过后的数组，并不是有序的，旋转之后只能保证数组局部是有序的，但是不妨碍继续使用二分查找

因为进行旋转之后，根据旋转点将数组分开的时候，一定有一部分是有序的，如示例数组为 [4,5,6,7,0,1,2] ，如果拿6来当旋转点，则旋转之后的数组被分成了两部分，分别为[4，5，6]，[7,0,1,2]，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此

即算法的核心思路为：

将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环…即不停的二分，二分完接着二分，一分为二后，有序的使用二分查找法，无序的继续二分

即在二分查找时，可以查看当前mid（即数组的中间）为旋转点时，分割出来的两个部分[l，mid]，[mid+1，r]哪个部分是有序的，并且根据有序的那个部分继续去改变二分查找的上下界，因为可以通过有序的那部分判断target在不在这部分中：

• 如果[l，mid-1]是有序数组，即左边有序，且target的大小满足[nums[l],nums[mid])，左闭右开，则应该将搜索范围缩小至[l，mid-1]，否则在[mid + 1, r]中找
• 如果[mid , r]是有序数组，且target大小满足(nums[mid+1],nums[r]]，则应该将搜索范围缩小至[mid + 1, r]，否则在[l, mid - 1]中寻找

这里举个例子：
如[4,5,6,7,0,1,2]，mid = 3，即查看下标为3的位置为分割点，[l，mid-1]对应的数组值为[4，5，6]，是有序的，以target = 5为例，target = 5满足这个范围，所以继续在这里面查找；以target = 2为例，target = 2不满足这个范围，即在[mid + 1, r]为[0,1,2]中寻找，此时已经是有序的了，可以直接用常规的二分

再如：[6,7,0,1,2,3,4,5]，mid = 3 即查看下标为3的位置为分割点，，[l，mid-1]对应的数组值为[6，7，0]，是无序的，所以看另一部分，[mid , r]对应的数组值为[1，2，4，5]，是有序的，以target = 4为例，target = 4在这个范围内，可以继续查找；以target = 6为例，target = 6不满足这个范围，所以在[l，mid-1]里面找，即数组变成了[6，7，0]，此时是无序的，继续找mid分成有序的和可能有序的两部分，继续二分…

java代码如下：

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        // 1. 首先明白，旋转数组后，从中间划分，一定有一边是有序的。
        // 2. 由于一定有一边是有序的，所以根据有序的两个边界值来判断目标值在有序一边还是无序一边
        // 3. 这题找目标值，遇到目标值即返回
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + (r - l ) / 2;//防止溢出
            if (nums[mid] == target) {
                return mid;//如果找到target的话在这里返回最终结果，否则返回-1
            }
            if (nums[l] <= nums[mid]) {//如果左边有序
                if (target >= nums[l] && target < nums[mid]) {//且target的大小满足[nums[l],nums[mid]),左开右闭
                    r = mid - 1;//则应该将搜索范围缩小至[l，mid-1]
                } else {
                    l = mid + 1;//否则在[mid + 1, r]中找
                }
            } else {//如果右边有序
                if (target > nums[mid] && target <= nums[r]) {//且target大小满足(nums[mid+1],nums[r]]
                    l = mid + 1;//则应该将搜索范围缩小至[mid + 1, r]
                } else {//否则在[l, mid - 1]中寻找
                    r = mid - 1;
                }
            }
        }
        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
35