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

pythonserver side programmingprogramming更新于 2025/11/22 17:48:17

假设我们有一个按升序排序的数组。该数组以我们事先不知道的某个枢轴旋转。例如，如果数组为 [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 := 数组大小
while 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 &miinus; 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):
      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))