find_first_missing_n.py

def find_missing(n_list):
    """Finds first missing number from list."""
    # At bottom of search
    if len(n_list) == 2:
        # If there were no missing numbers we're at the rightmost part. The
        # numbers will still in be in sequence, 1 apart. We find the max
        # between the lowest missing number and `1` to account for the lowest
        # missing number being below zero.
        if n_list[0] + 1 == n_list[1]:
            return max(n_list[1] + 1, 1)
        return max(n_list[0] + 1, 1)

    # the expected value is the number's position and the actual value
    mid_pos = int(len(n_list) / 2)
    mid_expectation = mid_pos + n_list[0]
    mid_reality = n_list[mid_pos]

    # decides what direction to cut towards
    if mid_reality > mid_expectation:
        # missing number to left
        missing_n = find_missing(n_list[0 : mid_pos + 1])
    else:
        # missing number to right
        missing_n = find_missing(n_list[mid_pos:])
    return missing_n


def clean_list(in_list):
    """Removes duplicates, sorts list"""
    return list(sorted(set([i for i in in_list])))


def main(n_list):
    """Calls cleaning and sorting functions"""
    cleaned_list = clean_list(n_list)
    if max(cleaned_list) < 1: # if all numbers below 0, return 1
        return 1
    missing_n = find_missing(cleaned_list)
    return missing_n


def tests():
    assert main([1, 2, 4, 5, 6]) == 3
    assert main([1, 2, 4, 5]) == 3
    assert main([-1, 2, 3, 4]) == 1
    assert main([5, 4, 3, 1]) == 2
    assert main([i for i in range(100000) if i != 42]) == 42  # size: 100,000
    assert main([i for i in range(99900, 1000000) if i != 99956]) == 99956
    assert main([1, 3, 6, 4, 1, 2]) == 5
    assert main([1, 2, 3]) == 4
    assert main([-1, -3]) == 1


if __name__ == "__main__":
    tests()