本文主要是介绍leetcode 84 Search in Rotated Sorted Array II 二分循环变种，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: falseFollow up:
- This is a follow up problem to Search in Rotated Sorted Array, where
numsmay contain duplicates. - Would this affect the run-time complexity? How and why?
--------------------------------------------------------------------------------------------------
这题在target和mid比较完之后，就陷入了和left和right大小的讨论，稍有不慎就会出错。因此，有两种解法：
解法一：两次二分
解法一：两次二分：第一次二分找到上图中max min的位置（leetcode 153 154 Find Minimum in Rotated Sorted Array I II 二分砍掉一边跨步移动，不找分界线_taoqick的博客-CSDN博客）。但是注意如果找到这个位置是0，还需要从数组末尾往前再看一段，防止dup的坑。
class Solution:def search(self, nums, target) -> int:def find_target(arr, lo, hi, tgt):l,r = lo,hiwhile (l <= r):mid = l + ((r-l)>>1)if (arr[mid] == tgt):return Trueif (tgt < arr[mid]):r = mid-1elif (arr[mid] < tgt):l = mid+1return False #since arr[lo] < target, l at least lo_1def find_min_pos(arr):l, r = 0, len(arr) - 1while (l < r and arr[l] == arr[r]):l += 1while (l <= r):mid = l + ((r-l)>>1)if (arr[mid] < arr[r]):r = midelif (arr[mid] > arr[r]):l = mid+1else:r -= 1return lif (not nums):return Falsemin_pos = find_min_pos(nums)#print("min_pos={0}".format(min_pos))if (nums[min_pos] > target):return Falseelif (nums[min_pos-1] < target):return Falseelif (min_pos == 0):return find_target(nums, 0, len(nums)-1, target)elif (target >= nums[0]):return find_target(nums, 0, min_pos-1, target)else:return find_target(nums, min_pos, len(nums)-1, target)
s = Solution()
print(s.search([1,1,3,1], 3))解法二：一次二分
关键在于点：当存在l<r且nums[l]<=nums[r]时，意味着下标是l到r之间的数都在[nums[l],nums[r]]这个范围，也就是说明这中间没有坑；当存在l<r且nums[l]>nums[r]时，意味着这中间有坑，也就是这中间不存在(nums[l],nums[r])这个范围的数
class Solution:def search(self, nums: List[int], target: int) -> bool:l,r = 0,len(nums)-1while (l<=r):mid=l+((r-l)>>1)if nums[mid] == target:return Truewhile (l<mid and nums[l]==nums[mid]):l += 1while (mid<r and nums[r]==nums[mid]):r -= 1# if (nums[mid] >= nums[r]): #不行# if (nums[l] < nums[mid]): #不行# if (nums[l] <= nums[mid]): #行了，等的情况扔给判断和target相等的那边if (nums[mid] > nums[r]): #也行，等的情况扔给判断和target相等的那边if (nums[l]<=target and target<nums[mid]):# 左边没有坑，且目标就在左边r = mid-1else:l = mid+1else:if (nums[mid]<target and target<=nums[r]):# 右边没有坑，且目标就在右边l = mid+1else:r = mid-1return False变种一：在一个rotated 可以重复数组中找<=target的最大元素值
这题还有一个变种，在一个rotated 可以重复数组中找<=target的最大元素值。利用解法一可以迅速简化：
import randomclass Solution:def lower(self, nums, target):lst = [num for num in nums if num <= target]return max(lst) if lst else Nonedef search(self, nums, target) -> int:def find_target(arr, lo, hi, tgt):l, r = lo, hiwhile (l <= r):mid = l + ((r - l) >> 1)if (arr[mid] == tgt):return tgtif (tgt < arr[mid]):r = mid - 1elif (arr[mid] < tgt):l = mid + 1return arr[l - 1] # since arr[lo] < target, l at least lo+1def find_min_pos(arr):l, r = 0, len(arr) - 1while (l < r and arr[l] == arr[r]): #针对bug1的另外一种fix方式l += 1while (l <= r):mid = l + ((r - l) >> 1)if (arr[mid] < arr[r]):r = midelif (arr[mid] > arr[r]):l = mid + 1else:r -= 1# if (l == 0): # bug1# pos = len(arr)# while (pos >= 1 and arr[pos - 1] == arr[0]):# pos -= 1# return 0 if (pos == len(arr)) else posreturn lif (not nums): # bug2return Nonemin_pos = find_min_pos(nums)# print("min_pos={0}".format(min_pos))if (nums[min_pos] > target):return Noneelif (nums[min_pos - 1] < target):return nums[min_pos - 1]elif (min_pos == 0):return find_target(nums, 0, len(nums) - 1, target)elif (target >= nums[0]):return find_target(nums, 0, min_pos - 1, target)else:return find_target(nums, min_pos, len(nums) - 1, target)s = Solution()
cols = 500for _ in range(1000):mid, target = random.randint(0, cols), random.randint(-10, cols + 10)raw = sorted([random.randint(1, cols) for i in range(cols)])arr = raw[mid:] + raw[:mid]# print('target={0} arr={1}'.format(target, arr))r1 = s.lower(arr, target)r2 = s.search(arr, target)if (r1 != r2):print("Error r1:{0} r2:{1}".format(r1, r2))print('target={0} arr={1}'.format(target, arr))
print('Finished!!!')变种二：有序数组截成三段，交换第一段和第三段，然后给一个数据进行二分查找
import random
from typing import Listclass Solution:def brute_force(self, nums, target):return target in numsdef search(self, nums: List[int], target: int) -> bool:l, r = 0, len(nums) - 1while (l <= r):mid = l + ((r - l) >> 1)if nums[mid] == target:return Truewhile (l < mid and nums[l] == nums[mid]):l += 1while (mid < r and nums[r] == nums[mid]):r -= 1if (nums[l] <= nums[mid]):# 左边没有坑if (nums[l] <= target and target < nums[mid]):r = mid - 1else:l = mid + 1elif (nums[mid] <= nums[r]):# 右边没有坑if (nums[mid] < target and target <= nums[r]):l = mid + 1else:r = mid - 1elif (nums[l] > nums[mid] and nums[mid] > nums[r]):# 两边都有坑，l,mid，r三个点，切割成4部分，分别讨论if target <= nums[r]:l = mid + 1elif target >= nums[l]:r = mid - 1elif nums[mid] > target and target > nums[r]:# 右边有坑，坑范围内的一定不可以r = mid - 1elif nums[l] > target and target > nums[mid]:# 左边有坑，坑范围内的一定不可以l = mid + 1return False
s = Solution()
cols = 10for _ in range(1000):mid1, target = random.randint(0, cols-1), random.randint(-10, cols + 10)mid2 = random.randint(mid1+1, cols)raw = sorted([random.randint(1, cols) for i in range(cols)])arr = raw[mid2:] + raw[mid1:mid2] + raw[:mid1]# print('target={0} arr={1}'.format(target, arr))r1 = s.brute_force(arr, target)r2 = s.search(arr, target)if (r1 != r2):print("Error r1:{0} r2:{1}".format(r1, r2))print('target={0} arr={1}'.format(target, arr))
print('Finished!!!')这篇关于leetcode 84 Search in Rotated Sorted Array II 二分循环变种的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
