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

让我们看看步骤 -

  • low := 0 且 high := 数组大小

  • 当 low < high 时

    • mid := low + (high - low)/2

    • 如果 nums[mid] = target，则返回 true

    • 如果 nums[low] = nums[mid] 且 nums[high - 1] = nums[mid]，则

      • 将 low 增加 1 并将 high 减少 1，并继续进行下一轮迭代

    • 如果 nums[low] <= nums[mid]，则

      • 如果 target >= nums[low] 且 target < nums[mid]，则 high := mid，否则 low := mid + 1

    • 否则

      • 如果 target <= nums[high - 1] 且 target > nums[mid]，则 low := mid + 1，否则 high := mid

    • 返回 false

示例

让我们看看下面的实现以更好地理解 -

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

更新于: 2020-02-03

176 次浏览

启动你的 职业生涯

通过完成课程获得认证

开始学习
广告