Finding missing items in an int list Here is a problem I am trying to solve: trying to find missing photographs from a sequence of filenames. The problem boils down to: given an unsorted list of integers, return a sorted list of missing numbers. Below is my code.

What I am looking for are:


Are there more efficient algorithms?
Is there any performance problem if the list is large (tens of thousands)
Corner cases which does not work?

def find_missing_items(int_list):
    '''
    Finds missing integer within an unsorted list and return a list of 
    missing items

    &gt;&gt;&gt; find_missing_items([1, 2, 5, 6, 7, 10])
    [3, 4, 8, 9]

    &gt;&gt;&gt; find_missing_items([3, 1, 2])
    []
    '''

    # Put the list in a set, find smallest and largest items
    original_set  = set(int_list)
    smallest_item = min(original_set)
    largest_item  = max(original_set)

    # Create a super set of all items from smallest to largest
    full_set = set(xrange(smallest_item, largest_item + 1))

    # Missing items are the ones that are in the full_set, but not in
    # the original_set
    return sorted(list(full_set - original_set))

if __name__ == '__main__':
    import doctest
    doctest.testmod()
For this

full_set = set(xrange(smallest_item, largest_item + 1))


I'd suggest inlining the min and max:

full_set = set(xrange(min(original), max(original) + 1))


You don't need to convert to a list before using sorted so:

sorted(list(full_set - original_set))


Can be written as:

sorted(full_set - original_set)