Missing Score Milestone
Context
In the game Neon Climb, completed score milestones are stored in increasing order. Milestone 0 is the first possible milestone, and later milestones normally increase one at a time. One milestone may be absent. Determine the smallest nonnegative milestone number that does not appear in the stored list.
Problem
Given the increasing list of completed score milestones, return the smallest nonnegative integer that is absent. Use the list's index relationship with the expected consecutive milestone value to guide a recursive binary search. If a midpoint still matches the consecutive pattern, the missing milestone must be later. Otherwise, keep the earlier half where the first gap can occur. An empty list means milestone 0 is missing, while a complete prefix returns the next milestone after that prefix.
Examples
milestones = []0milestones = [0, 1, 2, 4, 5]3milestones = [0, 1, 2, 3]4Constraints
0 <= len(milestones) <= 1000000 <= milestones[i] <= 1000000 for every imilestones: strictly increasing- Types:
milestonesis int[]; result is int
Function signature
def find_missing_milestone(milestones: list[int]) -> int
milestoneslist[int]- Increasing nonnegative milestone numbers recorded by the game.
- returns int
- The smallest nonnegative integer that does not occur in milestones.
Adapted from MBPP problem task_627 (CC BY 4.0). Rewritten, extended and verified by Iksha.
Notes
- The recorded milestones are guaranteed to be strictly increasing, so repeated values do not occur.
- The missing value may be before the first entry, between entries, or immediately after the final entry.