Python Forum

Please help me understand the code and its output

Find the missing element:
Given a sorted list or array, find a more efficient way to identify the element that is missing.
Below are code snippets from two files (findMissing.py and findMissingTest.py), create a
directory with these files and code snippets in them. If you run “python -m unittest
findMissingTest” from terminal or cmd you should see the test fail. Modify the function in
“findMissing.py” to make the test pass.
findMissing.py

#the idea here was to get mid of the array
#now if the distance of mid from starting is not equal to distance of starting, 
#it means missing element is left side
#similarly it may be on right side
#if not the case in both the answer will be no missing element
def findMissing(arr):
    #get start index
    start = 0
    #get end index
    end = len(arr) - 1
    #get mid
    mid = 0
    #loop until start +1 is less than end
    while (start + 1 < end): 
       #floor division
        mid = (start + end) // 2
        #If the missing number is less than mid, go through the left side
        if (arr[start] - start) != (arr[mid] - mid): 
            end = mid 
        #else missing number is on the right side
        elif (arr[end] - end) != (arr[mid] - mid): 
            start = mid
        if(start + 1 == end):
            return arr[mid] + 1
    raise ValueError(msg = "No missing element")

findMissingTest.py

import unittest
from timeit import default_timer
from sys import version_info
from findMissing import findMissing
class StringCalculatorTests(unittest.TestCase):
    def test_findMissing(self):
        missing = 60000123
        print("Missing element actual : "+str(missing))
        arr = list(range(100000000))
        arr.remove(missing)
        start_time = default_timer()
        result = findMissing(arr)
        end_time = default_timer()
        print("Algo Missing element : "+str(result))
        print("Time took to find missing element is : %15f"%(end_time-start_time)+" seconds")
        if version_info.major == 2:
            self.assertGreater(2, end_time - start_time)
        elif version_info.major == 3:
            self.assertGreater(2.5, end_time - start_time)
            self.assertEqual(missing, result)

Output:
PS C:\Users\slee5\Desktop\Code> python -m unittest findMissingTest.py
Missing element actual : 60000123
Algo Missing element : 60000123
Time took to find missing element is : 0.008799 seconds
.
----------------------------------------------------------------------
Ran 1 test in 25.192s

OK
PS C:\Users\slee5\Desktop\Code>

The idea is easy to understand, take the list

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

If you remove 0, 1, 2, 3 or 4, then L[4] has value 5. On the other hand, if you remove 5, 6, 7, 8 or 9, then L[4] has value 4. Hence by checking the value of L[4], you can say if the missing value is in range(0, 5) or in range(5, 10). The algorithm then repeats the same argument for the subarrays.

It looks like the test is already passing. The output doesn't show a failure.