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

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

from bisect import bisect_left

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

"""Doctest

>>> find_missing([1,2,3,5,6,7], 1, 7)

[4]
>>> find_missing([2,3,6,4,8], 2, 8)

[5, 7]
>>> find_missing([1,2,3,4], 1, 4)

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

[10]
>>> find_missing([-1,0,1,3,7,20], -1, 7)

[2, 4, 5, 6]

>>> find_missing([-2,0,3], -5, 2)

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

>>> find_missing([2],4,5)

[4, 5]

>>> find_missing([3,5,6,7,8], -3, 5)

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

>>> 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 & max values currently exist
#If they do not then add them to the resultant array as they are missing numbers
if min_val < first_in_int_array:            
    int_array.insert(0, min_val)
    result.append(min_val)

if max_val > last_in_int_array:
    int_array.insert(len(int_array), max_val)
    result.append(max_val)

#Dealing with case where max_val < 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)
    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

from bisect import bisect_left

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

"""Doctest

>>> find_missing([1,2,3,5,6,7], 1, 7)

[4]
>>> find_missing([2,3,6,4,8], 2, 8)

[5, 7]
>>> find_missing([1,2,3,4], 1, 4)

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

[10]
>>> find_missing([-1,0,1,3,7,20], -1, 7)

[2, 4, 5, 6]

>>> find_missing([-2,0,3], -5, 2)

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

>>> find_missing([2],4,5)

[4, 5]

>>> find_missing([3,5,6,7,8], -3, 5)

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

>>> 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 & max values currently exist
#If they do not then add them to the resultant array as they are missing numbers
if min_val < first_in_int_array:            
    int_array.insert(0, min_val)
    result.append(min_val)

if max_val > last_in_int_array:
    int_array.insert(len(int_array), max_val)
    result.append(max_val)

#Dealing with case where max_val < 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

I have an alternative algorithm to the same problem: Finding missing items in an int 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 & max because I heard that they has O-n efficiency

However I used the .index method for lists. I am not sure how efficient .index is. I would think that it would be O-log n for a sorted but I am not sure if/how the .index function would know that a given list is sorted

Additionally, I used Exceptions which do give a performance penalty

Thanks

1. 1 missing number - normal

2. Multiple Missing Numbers - normal

3. No missing numbers - normal

4. Repeats - normal

5. Array too small - Case for empty array: returns an array of the numbers from min_val to max_val inclusive

6. Missing numbers at end - Filled in based on the min and max number

7. Numbers out of range - Ignored those which were out of range

I have an alternative algorithm to the same problem as Finding missing items in an int 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.

1. One missing number - Normal

2. Multiple Missing Numbers - Normal

3. No missing numbers - Normal

4. Repeats - Normal

5. Array too small - Case for empty array: returns an array of the numbers from min_val to max_val inclusive

6. Missing numbers at end - Filled in based on the min and max number

7. Numbers out of range - Ignored those which were out of range