「力扣」第 81 题：搜索旋转排序数组 II（中等）
题解地址：二分查找（Python 代码、Java 代码）。
传送门：81. 搜索旋转排序数组 II。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0, 0, 1, 2, 2, 5, 6]可能变为[2, 5, 6, 0, 0, 1, 2])。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回
true，否则返回false。示例 1：
输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true示例 2：
输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false进阶：
这是搜索旋转排序数组的延伸题目，本题中的
nums可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
题目给出的是“旋转排序数组”，是“部分有序数组”，我们同样可以一次排除一半或者一半以上元素的方法，即二分查找法。
思路
二分查找法的本质是排除法，二分只是手段，二分保证了“熵”最大，即在没有任何有效信息的时候，平分是最好的方案。
思路清楚了以后，我们就得确定“有序数组”存在在“原始数组”的哪个子区间里，下面提供了两个比较标准：
1、中间元素和左边界比较；
2、中间元素和右边界比较。
由这两个比较标准就能写出两版不同的代码。
方法：二分查找
参考代码 1：中间元素和左边界比较
Java 代码：
public class Solution {
public boolean search(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return false;
}
int left = 0;
int right = len - 1;
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] > nums[left]) {
if (nums[left] <= target && target <= nums[mid]) {
// 落在前有序数组里
right = mid;
} else {
left = mid + 1;
}
} else if (nums[mid] < nums[left]) {
// 让分支和上面分支一样
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid;
}
} else {
// 要排除掉左边界之前，先看一看左边界可以不可以排除
if (nums[left] == target) {
return true;
} else {
left = left + 1;
}
}
}
// 后处理，夹逼以后，还要判断一下，是不是 target
return nums[left] == target;
}
}Python 代码：
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> bool:
size = len(nums)
if size == 0:
return False
left = 0
right = size - 1
while left < right:
mid = (left + right) >> 1
if nums[mid] > nums[left]:
if nums[left] <= target <= nums[mid]:
# 落在前有序数组里
right = mid
else:
left = mid + 1
elif nums[mid] < nums[left]:
# 让分支和上面分支一样
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid
else:
# 要排除掉左边界之前，先看一看左边界可以不可以排除
if nums[left] == target:
return True
left = left + 1
# 后处理，夹逼以后，还要判断一下，是不是 target
return nums[left] == target参考代码 2：中间元素和右边界比较
Java 代码：
public class Solution {
// 中间的数与右边界比较
public boolean search(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return false;
}
int left = 0;
int right = len - 1;
while (left < right) {
int mid = (left + right + 1 ) >>> 1;
if (nums[mid] < nums[right]) {
// 10 11 4 5 6 7 8 9
// 右边的一定是顺序数组，包括中间数
if (nums[mid] <= target && target <= nums[right]) {
left = mid;
} else {
right = mid - 1;
}
} else if (nums[mid] > nums[right]) {
// 4 5 9 2
// 左边是一定是顺序数组，包括中间数
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid;
}
}else {
if(nums[right] == target){
return true;
}
right = right -1;
}
}
return nums[left] == target;
}
}Python 代码：
from typing import List
# 中间元素和右边界比较
class Solution:
def search(self, nums: List[int], target: int) -> bool:
size = len(nums)
if size == 0:
return False
left = 0
right = size - 1
while left < right:
# mid = left + (right - left + 1) // 2
mid = (left + right + 1) >> 1
if nums[mid] < nums[right]:
# 后面是有序的
# [2,3,4,5,5,6,6,7]
if nums[mid] <= target <= nums[right]:
left = mid
else:
right = mid - 1
elif nums[mid] > nums[right]:
# [3,4,5,5,6,6,7,2]
if nums[left] <= target <= nums[mid - 1]:
right = mid - 1
else:
left = mid
else:
assert nums[mid] == nums[right]
if nums[right] == target:
return True
# 右边不是才删除
right = right - 1
# 后处理
return nums[left] == targetJava 代码：
public class Solution {
// [2,5,6,0,0,1,2]
// [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,5,6,0,0,1,2]
// 传统的二分查找法，与右边界比较
public boolean search(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return false;
}
int left = 0;
int right = len - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[mid] == nums[right]) {
right--;
} else if (nums[mid] < nums[right]) {
// mid 到 right 是顺序数组
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
// nums[mid] > nums[right]
// left 到 mid 是顺序数组
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return false;
}
}（本节完）
