Find missing element in a sorted array of consecutive numbers | Function to return the missing element ; Check if middle element is consistent ; No inconsistency till middle elements When missing element is just after the middle element ; Move right ; Inconsistency found When missing element is just before the middle element ; Move left ; No missing element found ; Driver code
def findMissing ( arr , n ) : NEW_LINE INDENT l , h = 0 , n - 1 NEW_LINE mid = 0 NEW_LINE while ( h > l ) : NEW_LINE INDENT mid = l + ( h - l ) // 2 NEW_LINE if ( arr [ mid ] - mid == arr [ 0 ] ) : NEW_LINE INDENT if ( arr [ mid + 1 ] - arr [ mid ] > 1 ) : NEW_LINE INDENT return arr [ mid ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT l = mid + 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( arr [ mid ] - arr [ mid - 1 ] > 1 ) : NEW_LINE INDENT return arr [ mid ] - 1 NEW_LINE DEDENT else : NEW_LINE INDENT h = mid - 1 NEW_LINE DEDENT DEDENT DEDENT return - 1 NEW_LINE DEDENT arr = [ - 9 , - 8 , - 7 , - 5 , - 4 , - 3 , - 2 , - 1 , 0 ] NEW_LINE n = len ( arr ) NEW_LINE print ( findMissing ( arr , n ) ) NEW_LINE