在C ++中搜索旋转排序数组II
考虑我们有一个按升序排序的数组。它以我们事先不知道的某个枢轴旋转。例如，如果数组类似于[0,0,1,2,2,5,6]，则可能变为[2,5,6,0,0,1,2]。我们有一个目标值要搜索。如果在数组中找到该值，则返回true，否则返回false。因此，如果数组类似于[2,5,6,0,0,1,2]，并且目标为0，那么输出将为0
让我们看看步骤-
低：=0和高：=数组大小
从低到高
如果目标<=nums[high-1]并且目标>nums[mid]，则低：=中+1，否则高：=中
如果目标>=nums[low]而目标<nums[mid]，则为高：=中，否则为低：=中+1
将low增加1，将high减少1，并继续进行下一次迭代
中：=低+（高-低）/2
如果nums[mid]=目标，则返回true
如果nums[low]=nums[mid]和nums[high-1]=nums[mid]，则
如果nums[low]<=nums[mid]，则
除此以外
返回假
示例
让我们看下面的实现以更好地理解-
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
low = 0
high = len(nums)
while low<high:
mid = low + (high-low)//2
print(mid)
if nums[mid] == target:
return True
if nums[low] == nums[mid] and nums[high-1] == nums[mid]:
low +=1
high -=1
continue
if nums[low]<=nums[mid]:
if target >=nums[low] and target <nums[mid]:
high = mid
else:
low = mid+1
else:
if target<=nums[high-1] and target>nums[mid]:
low = mid+1
else:
high = mid
return False输入值
[2,5,6,0,0,1,2] 0
输出结果
true