Python에서 회전 정렬된 배열 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 :=배열 크기
• 낮은 동안 <높음
  • 중간 :=낮음 + (높음 - 낮음)/2
  • nums[mid] =target이면 true를 반환합니다.
  • nums[low] =nums[mid] 및 nums[high - 1] =nums[mid]이면
    • 낮은 값을 1씩 늘리고 높은 값을 1씩 줄이고 다음 반복을 위해 계속
  • nums[low] <=nums[mid]이면
    • 대상>=nums[low] 및 대상 &miinus; nums[mid], high :=mid, 그렇지 않으면 low :=mid + 1
  • 그렇지 않으면
    • 대상 <=nums[high - 1]이고 target> nums[mid]이면 low :=mid + 1, 그렇지 않으면 high :=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