【Leetcode】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) 的算法解决此问题。

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

思路分析

这个题目因为要求时间复杂度为$O(logN)$ ，因此不能使用简单的顺序遍历查找。
容易想到使用经典的查找算法——二分查找法。这也是最常用的查找算法。

二分查找法应用的前提：（1）采用顺序存储结构。例如数组，这样才能够在O(1)的时间复杂度内通过下标随机访问到对应位置的元素，因此不能在链表上应用二分查找。（2）按关键字大小有序排列。如果数组不是有序的，可以先用排序算法将数组元素排好序。

回顾二分查找算法的一般形式：

def bi_search(nums, target):
	l, r = 0, len(nums)-1 # 初始化左边界和右边界
	while l <= r:  # 每次遍历l向右移或r向左移，当l>r说明l移动到r右边，已经没有待查找区间了，停止遍历
		mid = (l + r)>>1  # 找到中间节点，将待查找区间一分为二，根据判断target与nums中间位置的元素的大小判断往哪边缩小查找区间
		if target == nums[mid]:  # 查找到target的情形就是：查找区间缩小为单个元素且该元素就是target本身
			return mid
		elif target < nums[mid]:  # 若target大于中间位置的元素，则在大于target的范围内继续查找
			r = mid - 1
		else:  # 若target小于中间位置的元素，则在小于target的范围内继续查找
			l = mid + 1
	return -1  # 最后确定的最小查找区间（单个元素）没有target，即没查找到target
1
2
3
4
5
6
7
8
9
10
11

对于该问题，并不能直接应用二分查找法。因为nums 在预先未知的某个下标上进行了旋转，所以旋转节点所在的区间是非顺序的，不满足二分查找法的前提。需要加以改进。

对于本问题，我们需要分析旋转数组的特性，以准确判断下一步缩小查找区间的方向。
以旋转数组[4,5,6,7,8,9,0,1,2]为例，可以分为顺序区间[4,5,6,7]和非顺序区间[9,0,1,2]。容易发现，原数组中最大的几个元素和最小的几个元素都在非顺序区间；也因此 顺序区间的所有元素都要小于非顺序区间的左边界，顺序区间的所有元素都要大于非顺序区间的右边界。

taget仅与中间位置元素的大小比较不能作为判断与其他元素相对大小的准确依据，因为旋转数组的中间位置节点并不是整个数组的中位数。可能会向左偏移或向右偏移，仅当数组在下标0旋转（就等于没旋转）时才可以直接应用二分查找法（我们需要兼容该场景）。因此我们还需要补充判断target与其他边界元素的大小比较。

基于二分查找法，修改算法如下：
（由于左右两个区间可能有一个是非顺序的。非顺序区间在左或右）

• 若target等于中间位置元素：返回位置结果
• 若target小于中间位置元素：
  • 若右区间是非顺序区间（则左区间是顺序区间，由于非顺序区间中存在比顺序区间中更小的元素，还需要继续判断target到底是在顺序区间还是非顺序区间）：
    • 若target大于等于顺序区间的左边界：说明target在顺序区间内，下一个查找区间应为顺序区间；
    • 否则说明target比顺序区间所有元素都要小，下一个查找区间应为非顺序区间；
  • 若左区间是非顺序区间：由于右区间是顺序区间都大于target，下一个查找区间应为非顺序区间；
• 若target大于中间位置元素：
  • 若左区间是非顺序区间（则右区间是顺序区间，由于非顺序区间中存在比顺序区间中更大的元素，还需要继续判断target到底是在顺序区间还是非顺序区间）：
    • 若target小于等于顺序区间的右边界：说明target在顺序区间内，下一个查找区间应为顺序区间；
    • 否则说明target比顺序区间所有元素都要大，下一个查找区间应为非顺序区间；
  • 若右区间是非顺序区间：由于左区间是顺序区间都小于target，下一个查找区间应为非顺序区间；

注意判断条件中等号的处理：
因数组长度为偶数而中间位置为偏左一位的情况下，最后左边界可能与中间位置重合，因此当左边界与中间位置下标比较时需要加上等号判断；
如果target与左区间左边界比较后判断需要移动下一个查找区间到左区间，要包括target=左区间左边界的情况；同理如果target与右区间右边界比较后判断为需要移动下一个查找区间到右区间，要包括target=右区间右边界的情况；

总的来说，该问题的解法就是通过二分区间判断target的大小在哪个区间范围，然后在循环中不断细化下一个查找区间依照同样的逻辑判断选择，最后找到具体位置。

代码示例

class Solution:
    def search(self, nums, target):
        l, r = 0, len(nums)-1
        while l <= r:
        	mid = (l + r) >> 1
        	if target == nums[mid]:
        		return mid
        	elif target < nums[mid]:
        		if nums[l] <= nums[mid]:  # 左区间顺序区间，右区间非顺序区间。注意这里需加上=的判断，处理数组长度为偶数时最终左边界与中间位置重合的情况。
        			if target >= nums[l]: # target除了与nums[mid]比较，还需要与顺序区间的左边界比较，判断其在不在顺序区间内（包括刚好等于顺序区间左边界的情况）
                        r = mid - 1 # 在顺序区间内
                    else:
                        l = mid + 1  # 否则在非顺序区间
        		else:
        			r = mid - 1
        	else:  # target > nums[mid]:
        		if nums[mid] < nums[r]: # 右区间顺序区间，左区间非顺序区间
        			if target <= nums[r]: # target除了与nums[mid]比较，还需要与顺序区间的右边界比较，判断其在不在顺序区间内。（包括刚好等于顺序区间右边界的情况）
        				l = mid + 1  # 在顺序区间
        			else:  
        				r = mid - 1  # 否则在非顺序区间
        		else: # 左区间顺序区间，右区间非顺序区间。
        			l = mid + 1 
        return -1 # 未查找到target
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24