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