Python에서 회전 정렬 배열에서 검색

오름차순으로 정렬된 배열이 있고 사전에 알려지지 않은 일부 피벗에서 회전한다고 가정해 보겠습니다. 예를 들어, [0,1,2,4,5,6,7]은 [4,5,6,7,0,1,2]가 될 수 있습니다. 검색에 대상 값을 지정했습니다. 배열에서 얻을 수 있으면 인덱스를 반환하고, 그렇지 않으면 -1을 반환합니다. 배열에 중복 항목이 없다고 가정할 수 있습니다. 따라서 배열이 [4,5,6,7,0,1,2]와 같으면 출력은 4가 됩니다. 이 요소의 인덱스가 인덱스 4에 있기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

• low :=0 및 high :=배열 길이
• 낮은 동안 <높음
  • 중간을 중간으로 찾기 :=낮음 + (높음 - 낮음)/2
  • arr[mid] =target이면 mid를 반환합니다.
  • arr[low] <=arr[mid]
    인 경우
    • target>=arr[low]이고 target
  • 그렇지 않으면
    • target <=arr[high - 1]이고 target> arr[mid]이면 low :=mid + 1, 그렇지 않으면 high :=mid
• 반환 -1

예제(파이썬)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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 mid
         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 -1
ob1 = Solution()
print(ob1.search([4,5,6,7,8,0,1,2], 0))

입력

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

출력

5