Python의 정렬된 배열에서 요소의 첫 번째 및 마지막 위치 찾기

정수 A의 배열이 있다고 가정합니다. 이것은 오름차순으로 정렬되어 있으므로 주어진 대상 값의 시작 위치와 끝 위치를 찾아야 합니다. 배열에서 대상을 찾을 수 없으면 [-1, -1]을 반환합니다. 따라서 배열이 [2,2,2,3,4,4,4,4,5,5,6]이고 대상이 4인 경우 출력은 [4,7]

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

• 초기 res :=[-1,-1], low :=0, high :=배열 A의 길이로 설정
• 낮은 동안 <높음
  • 중간 :=낮음 + (높음 – 낮음)/2
  • A[mid]가 대상이면
    • 높음 :=중간, res[0] :=중간 및 res[1] :=중간
  • 그렇지 않으면 A[mid]
• res[0] =-1이면 res를 반환합니다.
• low :=res[0] + 1, high :=숫자 길이
• 낮은 동안 <높음
  • 중간 :=낮음 + (높음 – 낮음)/2
  • A[mid]가 대상이면
    • 낮음 :=중간 + 1, res[1] :=중간
  • 그렇지 않으면 A[mid]
• 반환 결과

예시(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def searchRange(self, nums, target):
      res = [-1,-1]
      low = 0
      high = len(nums)
      while low<high:
         mid = int(low + (high-low)//2)
         if nums[mid] == target:
            high = mid
            res[0]=mid
            res[1]=mid
         elif nums[mid]<target:
            low = mid+1
         else:
            high = mid
      if res[0] == -1:
         return res
      low = res[0]+1
      high = len(nums)
      while low<high:
         mid = int(low + (high-low)//2)
         if nums[mid] == target:
            low = mid+1
            res[1] = mid
         elif nums[mid] < target:
            low = mid + 1
         else:
            high = mid
      return res
ob1 = Solution()
print(ob1.searchRange([2,2,2,3,3,4,4,4,4,5,5,6], 4))

입력

[2,2,2,3,4,4,4,4,5,5,6]
4

출력

[5, 8]