原题地址:https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/
用循环遍历数组肯定能轻松找到target
但要尽可能减少操作步骤,一般跟顺序有关的都是用二分,关键是这题如何二分搜索
在找到中间位置mid后,数组被分成两个部分,一个有序一个无序,只要判断哪边是有序数组,然后再判断target是否在有序数组中,即可知道接下来要搜索哪一边。
如何判断哪一边是有序数组?可以把nums[mid]和nums[l]做比较,if now < nums[l] 右边有序,反之 左边有序
但还是会出现一个问题。就是重复如果now == nums[l],该怎么办?此时就把l右移一位即可(+1)
''' 二分后一边有序一边无序,看target是否在有序的那一边的范围内 ''' class Solution: def search(self, nums: List[int], target: int) -> bool: l, r = 0, len(nums) - 1 while l <= r: mid = (l + r) // 2 now = nums[mid] if now == target: return True if now < nums[l]: # 右边有序 if now < target and target <= nums[r]: l = mid + 1 else: r = mid - 1 elif now > nums[l]: # 左边有序 if nums[l] <= target and target < now: r = mid - 1 else: l = mid + 1 else: l = l + 1 return False
标签:数组,nums,II,搜索,有序,81,leetcode,target From: https://www.cnblogs.com/gogslow/p/16635936.html