Pythonで連続番号のソートされた配列から欠落している要素を見つける

n個の一意の番号の配列Aがあり、これらのn個の要素は昇順で配列に存在しますが、欠落している要素が1つあるとします。不足している要素を見つける必要があります。

したがって、入力がA =[1、2、3、4、5、6、7、9]の場合、出力は8になります。

これを解決するには、次の手順に従います-

• n：=Aのサイズ

• 左：=0

• 右：=n-1

• mid：=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]

出力

8