Find Missing Numbers in an int list I have an alternative algorithm to the same problem as Finding missing items in an int list.

My implementation includes optional min and max bounds to selectively fill in the list.

The linked implementation is much simpler.

My Questions are:


How do our two algorithms compare, efficiency wise?
Besides the algorithm linked, are there more efficient algorithms?
Did I identify and does my algorithm work for the edge cases?




I tried not to use min and max because I heard that they are \$\mathcal{O}(n)\$.

However, I used the .index method for lists. I am not sure how efficient .index is. I would think that it would be \$\mathcal{O}(\log n)\$ for a sorted but I am not sure if or how the .index function would know that a given list is sorted.

Additionally, I used exceptions, which do give a performance penalty.

7 Cases


One missing number - Normal
Multiple Missing Numbers - Normal
No missing numbers - Normal
Repeats - Normal
Array too small - Case for empty array: returns an array of the numbers from min_val to max_val inclusive
Missing numbers at end - Filled in based on the min and max number
Numbers out of range - Ignored those which were out of range




from bisect import bisect_left

def find_missing(int_array, min_val = False, max_val = False):

"""Doctest

&gt;&gt;&gt; find_missing([1,2,3,5,6,7], 1, 7)

[4]
&gt;&gt;&gt; find_missing([2,3,6,4,8], 2, 8)

[5, 7]
&gt;&gt;&gt; find_missing([1,2,3,4], 1, 4)

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

[10]
&gt;&gt;&gt; find_missing([-1,0,1,3,7,20], -1, 7)

[2, 4, 5, 6]

&gt;&gt;&gt; find_missing([-2,0,3], -5, 2)

[-5, -4, -3, -1, 1, 2]

&gt;&gt;&gt; find_missing([2],4,5)

[4, 5]

&gt;&gt;&gt; find_missing([3,5,6,7,8], -3, 5)

[-3, -2, -1, 0, 1, 2, 4]

&gt;&gt;&gt; find_missing([1,2,4])

[3]

"""
if len(int_array) == 0:
    return list(range(min_val, max_val+1))

int_array = sorted(int_array)
first_in_int_array = int_array[0]
last_in_int_array = int_array[len(int_array)-1]

if not min_val:
    min_val = first_in_int_array

if not max_val:
    max_val = last_in_int_array
result = []

#Checking to see if the min &amp; max values currently exist
#If they do not then add them to the resultant array as they are missing numbers
if min_val &lt; first_in_int_array:            
    int_array.insert(0, min_val)
    result.append(min_val)

if max_val &gt; last_in_int_array:
    int_array.insert(len(int_array), max_val)
    result.append(max_val)

#Dealing with case where max_val &lt; last_in_int_array but not in array 
#Example: max_val = 2 int_array = [1,3]
#Also dealing with the analogous case for min_val and first_in_int_array
#Deal with this using exceptions
try:
    min_pos = int_array.index(min_val)

except Exception as e:
    result.append(min_val)
    min_pos = bisect_left(int_array, min_val)
    int_array.insert(min_pos, min_val)



try:
    max_pos = int_array.index(max_val)
except Exception as e:
    result.append(max_val)
    max_pos = bisect_left(int_array, max_val)
    int_array.insert(max_pos, max_val)


for i in range(min_pos,max_pos):
    difference = int_array[i+1] - int_array[i]
    if difference != 1 and difference != 0:
        result += range(int_array[i]+1,int_array[i+1])

result.sort()
return result
You say 'Doctest'  but then you format them badly with unecessary newlines and you do not actually run the tests.
Your code is much more complex than it should be.
When writing a programme remember that it should be the simplest possible.


The function down below behaves exactly like yours but:


It is 3 lines of code instead of 50.
The doctest is properly formatted so that you can actually run it.
The doctest is actually run when the script is executed as the main file.


:

import doctest

def find_missing(integers_list,start=None,limit=None):
    """
    Given a list of integers and optionally a start and an end, finds all
    the integers from start to end that are not in the list.

    'start' and 'end' default respectivly to the first and the last item of the list.

    Doctest:

    &gt;&gt;&gt; find_missing([1,2,3,5,6,7], 1, 7)
    [4]

    &gt;&gt;&gt; find_missing([2,3,6,4,8], 2, 8)
    [5, 7]

    &gt;&gt;&gt; find_missing([1,2,3,4], 1, 4)
    []

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

    &gt;&gt;&gt; find_missing([-1,0,1,3,7,20], -1, 7)
    [2, 4, 5, 6]

    &gt;&gt;&gt; find_missing([-2,0,3], -5, 2)
    [-5, -4, -3, -1, 1, 2]

    &gt;&gt;&gt; find_missing([2],4,5)
    [4, 5]

    &gt;&gt;&gt; find_missing([3,5,6,7,8], -3, 5)
    [-3, -2, -1, 0, 1, 2, 4]

    &gt;&gt;&gt; find_missing([1,2,4])
    [3]

    """
    start = start if start is not None else integers_list[0]
    limit = limit if limit is not None else integers_list[-1]
    return [i for i in range(start,limit + 1) if i not in integers_list]


def _test():
    doctest.testmod()

if __name__ == "__main__":
    _test()