继续打卡算法题，今天学习的是LeetCode的第81题搜索旋转排序数组 II，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。
分析一波题目
本题目是LeetCode第33题搜索旋转排序数组的升级版本，本题难点在于数组中有重复数值。
第33题已经说明旋转后的有序特点。
二分中间位置mid前的数据是严格递增的，这种情况和普通的二分求解一样。看目标数据在不在前半部分。
比如 0,0,1,2,2,5,6,7,8 在位置4旋转之后变成了2,5,6,7,8,0,0,1,2 第一次二分后，前半部分2,5,6,7,8 是严格递增的。这种情况二分搜索就好搜索了。
二分中间位置mid前的数据不是严格递增的，这种情况需要看目标数据在不在后半部分。后半部分是有序的。
再比如 比如 0,0,1,2,2,5,6,7,8 在位置6旋转变成了6,7,8,0,0,1,2,2,5 这样第一次二分后，前半部分 6,7,8,0,0是分两个阶段的，但是后半半部分1,2,2,5 是有序的。
而本题是数组中数字有重复，因此我们只要在33题的基础上加上去重就可以解决了。
本题解题技巧
1、二分法是搜索有序数组的，借助旋转后的特点，二分法同样可以搜索。本题需要注意去重逻辑
编码解决
class Solution {
public boolean search(int[] nums, int target) {
int n = nums.length;
if (n == 0) {
return false;
}
if (n == 1) {
return nums[0] == target ? true : false;
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return true;
//相同的数，去重
if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
++l;
--r;
} else if (nums[l] <= nums[mid]) {
//左边是严格递增的
//数据在左边
if (nums[l] <= target && target < nums[mid]) {
r = mid - 1;
} else {
//数据在右边
l = mid + 1;
}
} else {
//数据在右边
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
//数据在左边
r = mid - 1;
}
}
}
return false;
}
}
总结
1、本题的关键是理解两个旋转有序数组后的特点。
I. 二分中间位置mid前的数据是严格递增的，这种情况和普通的二分求解一样。看目标数据在不在前半部分。
II. 二分中间位置mid前的数据不是严格递增的，这种情况需要看目标数据在不在后半部分。
