在Python中搜索旋转排序数组II

  • Z时代
  • 2024-01-10
  • 分类：综合

考虑我们有一个按升序排序的数组。它以我们事先不知道的某个枢轴旋转。例如，如果数组类似于[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]而目标＆miinus; 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):
          low = 0
          high = len(nums)
          while low<high:
             mid = low + (high-low)//2
             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
    ob1 = Solution()print(ob1.search([2,5,6,0,0,1,2], 0))

    输入值

    [2,5,6,0,0,1,2]
    0

    输出结果

    True

    以上是 在Python中搜索旋转排序数组II 的全部内容， 来源链接： utcz.com/z/350316.html

    回到顶部