目录
简介
应用
应用1：Leetcode
题目
分析
方法一
旋转后的数组，就形成了两个有序的子数组。
因为左右两部分子数组都是有序的，所以，在局部查找的时候，依然可以使用二分查找的方式查找。
算法步骤
对于每次找到的区间中点 nums[mid] ：
-
如果它在右侧的子区间
-
如果目标值
target在[nums[0], nums[mid]]之间，则移动区间右侧的指针； -
否则，就移动区间左侧指针。
-
-
如果它在左侧的子区间
-
如果目标值
target在[nums[mid], nums[-1]]之间，则移动区间右侧的指针； -
否则，就移动区间左侧指针。
-
方法二
比较直观的思路是：因为目标值 target 是固定的，所以，我们直接考虑 target 落在左侧子区间，还是右侧子区间。
算法步骤
对于待查找的目标值 target ：
-
如果它落在右侧的子区间
-
如果区间中点
nums[mid]大于目标值target，或者区间中点nums[mid]小于nums[0]，则移动右侧指针； -
否则就移动左侧指针。
-
-
如果它落在左侧的子区间
-
如果区间中点
nums[mid]小于目标值target，或者区间中点nums[mid]大于等于nums[0]，则移动左侧指针； -
否则就移动右侧指针。
-
代码实现
方法一
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]:
if nums[0] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[len(nums)-1]:
left = mid + 1
else:
right = mid - 1
return -1
方法二
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if target >= nums[0]:
if nums[mid] > target or nums[mid] < nums[0]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target or nums[mid] >= nums[0]:
left = mid + 1
else:
right = mid - 1
return -1
应用2：Leetcode 81. 搜索旋转排序数组 II
题目
分析
当数组中存在重复元素时，二分查找时，可能会遇到这种情况：
\[nums[left] = nums[mid] = nums[right] \]此时，无法判断区间应该在左侧，还是右侧缩小。
例如，\(nums = [3,1,2,3,3,3,3,3], target = 2\)，第一次二分时，区间中点：\(nums[3] = 3\)，区间被分成两个子区间：\(nums[0\cdots2]=[3,1,2]\)，\(nums[4\cdots7]=[3,3,3,3]\)，此时，区间中点元素\(3\) 与左右边界元素相同。
这种情况，只需要同时缩小左右两侧的边界即可，即左边界加 1，右边界减 1，然后在新的区间上继续二分查找即可。
代码实现
class Solution:
def search(self, nums: List[int], target: int) -> bool:
n = len(nums)
if not nums:
return False
if n == 1:
return nums[0] == target
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return True
# 左右两侧元素，与区间中点元素相等，则同时移动左右指针
if nums[left] == nums[mid] and nums[right] == nums[mid]:
left += 1
right -= 1
elif nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[-1]:
left = mid + 1
else:
right = mid - 1
return False