image.png
0. 链接
1. 需求
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
2. 思路1: 先用二分法找到数组旋转点, 再从两部分数组中分别用二分法寻找
2.1 算法步骤
例如从nums=[4, 5, 6, 7, 0, 1, 2]中查找target=0
过程如下:
1) 先用二分法寻找到旋转点7对应下标split_index=3
2) 如果target < nums[0]
则从nums[0: split_index + 1]中二分查找target所处下标
否则
则从nums[split_index + 1:-1]中二分查找target所处下标result_index
如果结果不为-1，则返回split_index + 1 + result_index
2.2 代码
# coding:utf8
class Solution:
def binary_search(self, nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif target > nums[mid]:
left = mid + 1
elif target < nums[mid]:
right = mid - 1
return -1
def search_pivot(self, nums):
left = 0
right = len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[left] and nums[mid] > nums[right]:
left = mid
elif nums[mid] < nums[left] and nums[mid] < nums[right]:
right = mid
else:
break
return left
def search(self, nums, target: int) -> int:
if len(nums) == 0:
return -1
if nums[0] < nums[-1]:
return self.binary_search(nums, target)
pivot_index_left = self.search_pivot(nums)
if pivot_index_left == -1:
return -1
if target < nums[0]:
target_idx = self.binary_search(nums[pivot_index_left + 1:], target)
return pivot_index_left + 1 + target_idx if target_idx != -1 else -1
else:
return self.binary_search(nums[:pivot_index_left + 1], target)
solution = Solution()
print(solution.search([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(solution.search([], 1)) # -1
print(solution.search([1], 1)) # 0
print(solution.search([1, 3], 1)) # 0
print(solution.search([1, 3, 0], 0)) # 2
2.3 结果
image.png
3. 思路2: 只用一次二分查找解决问题
3.1 算法步骤
1. 已知数组含有两个分别有序的子数组,
2. 定义left=0, right=len(array) - 1,
while left <= right do
计算mid = (left + right) // 2,
如果 nums[mid] == target 则
返回mid
否则
判断mid处元素和target是否处于同一个子数组
1) 如果array[mid] >= nums[0] > target, 即mid处于左子数组, 而target处于右子数组, 此时需要
left = mid + 1, 试图接近target所处的位置
2) 如果array[mid] < nums[0] <= target, 即mid处于右子数组, 而target处于左子数组, 此时需要
right = mid - 1, 试图接近target所处的位置
3) 1和2都不满足, 则说明mid和target处于同一个子数组,此时可以走正常二分查找的步骤, 即:
if target < nums[mid]:
right = mid - 1
else:
left = mid + 1
return -1
3.2 代码
class SolutionSimple:
def search(self, nums, target):
if len(nums) == 0:
return -1
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] >= nums[0] > target:
left = mid + 1
elif nums[mid] < nums[0] <= target:
right = mid - 1
else:
if target > nums[mid]:
left = mid + 1
else:
right = mid - 1
return -1
solution = SolutionSimple()
print(solution.search([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(solution.search([], 1)) # -1
print(solution.search([1], 1)) # 0
print(solution.search([1, 3], 1)) # 0
print(solution.search([1, 3, 0], 0)) # 2
print(solution.search([4, 5, 6, 7, 0, 1, 2], 3)) # -1
3.3 结果
image.png
