旋转数组搜索专题
date
Nov 16, 2022
slug
reverse-list-search
status
Published
tags
算法
summary
如何在旋转数组中找到target
type
Post
简介
旋转数组搜索的题目，在leetcode上一共有四道，下面我们逐一分析每一道题目，一起看看能不能总结出相关的性质。
33. 搜索旋转排序数组
条件：
- 题目要求我们使用的方法解决题目，看到这个时间复杂度自然会想到二分了
- 数组是
distinct，也就是无重复元素的
- 数组原本是升序的
我们可以得知，升序数组经过旋转后必然是有断层的存在，如下图
下面我们列出想到的性质，看看能不能找到解决思路：
- 假设 m 是断层的顶点，那么有A[m] > A[m - 1]，A[m] > A[m + 1] 同时成立
- 不管数组的形态如何，A[0] > A[-1] 一定成立
- 数组始终被分为两部分有序的数组
性质1和2对我们帮助其实不大，我们看看性质3有没有突破点
我们进一步考虑更细致的状态，假设我们使用二分得到的顶点是m
此时A[0] < A[m]，我们可以得出[0, m]的区间一定是有序的
那么我们判断target是否处于这个区间即可，如果target位于[0, m]，那么我们让 j = m - 1，否则我们让i = m + 1
此时A[0] > A[m]，我们可以得出[m, n - 1]的区间一定是有序的
同样我们判断target是否处于这个区间即可，如果target位于[m, n - 1]，那么我们让 i = m + 1，否则我们让j = m - 1
从上图的分析看出，我们仍然可以根据A[0]和A[m]的大小关系，得到一段有序的区间，然后判断target和有序区间的大小关系，来二分。
其实二分并不要求单调性，二分的本质是边界性，比如这道题目，我们以m为边界，可以划分出两种区间[0, m]和[m, n - 1]，然后我们判断target是否落在区间，进一步就可以用m为边界来更新left 或 right，达到缩减问题规模的效果。
class Solution {
public int search(int[] nums, int target) {
int n = nums.length, i = 0, j = n - 1, m = 0;
if (n == 1) return nums[0] == target ? 0 : -1;
while (i <= j) {
m = i + j >> 1;
if (target == nums[m]) return m;
if (nums[0] <= nums[m]) {
if (nums[0] <= target && target < nums[m]) j = m - 1;
else i = m + 1;
} else {
if (nums[m] < target && target <= nums[n - 1]) i = m + 1;
else j = m - 1;
}
}
return -1;
}
}81. 搜索旋转排序数组 II
区别和1仅仅在于这里可能会有重复元素
我们当然想要借鉴题目1的解法，但是这里由于重复元素的情况存在，可能会导致A[0] = A[m]的情况存在，此时我们不能再二分了，因为没办法划出边界，只能让i += 1, j -= 1来做缩小边界区间，又由于发生了这样的移动，所以边界应该写成A[i]，而不是A[0]
class Solution {
public boolean search(int[] nums, int target) {
int n = nums.length, i = 0, j = n - 1, m = 0;
if (n == 1) return nums[0] == target ? true : false;
while (i <= j) {
m = i + j >> 1;
if (target == nums[m]) return true;
if (nums[i] == nums[m] && nums[m] == nums[j]) {
i ++;
j --;
}
else if (nums[i] <= nums[m]) {
if (nums[i] <= target && target < nums[m]) j = m - 1;
else i = m + 1;
} else {
if (nums[m] < target && target <= nums[n - 1]) i = m + 1;
else j = m - 1;
}
}
return false;
}