在Python中的连续数字排序数组中查找缺失的元素

假设我们有一个由n个唯一数字组成的数组A，这n个元素以升序出现在数组中，但是有一个缺失的元素。我们必须找到缺失的元素。

因此，如果输入类似于A = [1、2、3、4、5、6、7、9]，那么输出将为8。

为了解决这个问题，我们将遵循以下步骤-

• n：= A的大小

• 左：= 0

• 右：= n-1

• 中：= 0

• 当右>左时，执行

• 如果A [mid]-A [mid-1]> 1，则

• 除此以外，

• 返回A [mid]-1

• 右：=中-1

• 如果A [mid + 1]-A [mid]> 1，则

• 除此以外，

• 返回A [mid] +1

• 左：=中+ 1

• 中：=左+（右-左）/ 2

• 如果A [mid]-mid与A [0]相同，则

• 除此以外，

• 返回-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