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 :=배열 크기

• 낮음 <높음

  동안

  • 중간 :=낮음 + (높음 - 낮음)/2

  • nums[mid] =target이면 true를 반환합니다.

  • nums[low] =nums[mid] 및 nums[high - 1] =nums[mid]인 경우

    • 낮은 값을 1씩 증가시키고 높은 값을 1씩 감소시키고 다음 반복을 위해 계속하십시오.

  • nums[low] <=nums[mid]이면

    • target>=nums[low]이고 target

  • 그렇지 않으면

    • target <=nums[high - 1]이고 target> nums[mid]이면 low :=mid + 1, 그렇지 않으면 high :=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