Find the missing number in a sorted sequence of natural numbers.

Algorithms

Due to the fact that the array is sorted, each subsequent element is greater than the previous one by 1 and only one element is missing, we can use binary search, since before the missing int, all numbers in the sequence are equal to `index + sequence[0]`, and everything after the missing int is greater than the expression `index + sequence[0]` by 1.

Thus, the array is divided into two halves by the point at which "the right element is greater than its real value, and the left element corresponds to its real value."

Due to binary search, the time complexity of the algorithm is `O(log(n))`, and due to the fact that the "correct" value can be calculated from the formula, there is no need to construct a range as in the previous solutions.

Code
Diff
• ``````from typing import Sequence

def missing_integer(seq: Sequence[int]) -> int | None:
lo, hi = 0, len(seq)
while lo < hi:
mid = (lo + hi) // 2
real = seq[mid]
must_be = seq[0] + mid

if real > must_be:
if must_be - 1 == seq[mid - 1]:
return must_be
hi = mid

if real == must_be:
lo = mid + 1
``````
• from typing import Sequence, Optional
• from typing import Sequence
• def missing_integer(sequence: Sequence[int]) -> Optional[int]:
• for x, y in zip(sequence, range(sequence[0], sequence[-1])):
• if x != y:
• return y
• def missing_integer(seq: Sequence[int]) -> int | None:
• lo, hi = 0, len(seq)
• while lo < hi:
• mid = (lo + hi) // 2
• real = seq[mid]
• must_be = seq[0] + mid
• if real > must_be:
• if must_be - 1 == seq[mid - 1]:
• return must_be
• hi = mid
• if real == must_be:
• lo = mid + 1