Python에서 정렬된 연속 숫자 배열에서 누락된 요소 찾기

n개의 고유 숫자로 구성된 배열 A가 있다고 가정하고 이 n개의 요소는 배열에 오름차순으로 존재하지만 누락된 요소가 하나 있습니다. 누락된 요소를 찾아야 합니다.

따라서 입력이 A =[1, 2, 3, 4, 5, 6, 7, 9]와 같으면 출력은 8이 됩니다.

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

n :=A의 크기
왼쪽 :=0
오른쪽 :=n - 1
중간 :=0
동안 오른쪽> 왼쪽 , 수행
- 중간 :=왼쪽 +(오른쪽 - 왼쪽) / 2
- A[mid] - mid가 A[0]과 같으면
  - A[mid + 1] - A[mid]> 1이면
    - 반환 A[mid] + 1
  - 그렇지 않으면
    - 왼쪽 :=중간 + 1
- 그렇지 않으면
  - A[mid] - A[mid - 1]> 1이면
    - 반환 A[mid] - 1
  - 그렇지 않으면
    - 오른쪽 :=중간 - 1
반환 -1

예

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

def search_missing_item(A):
   n = len(A)
   left, right = 0, n - 1
   mid = 0
   while (right > left):
      mid = left + (right - left) // 2
   if (A[mid] - mid == A[0]):
      if (A[mid + 1] - A[mid] > 1):
         return A[mid] + 1
      else:
         left = mid + 1
      else:
         if (A[mid] - A[mid - 1] > 1):
            return A[mid] - 1
         else:
            right = mid - 1
   return -1

A = [1, 2, 3, 4, 5, 6, 7, 9]
print(search_missing_item(A))

입력

[1, 2, 3, 4, 5, 6, 7, 9]