Find closest number in array | Returns element closest to target in arr [ ] ; Corner cases ; Doing binary search ; If target is less than array element , then search in left ; If target is greater than previous to mid , return closest of two ; Repeat for left half ; If target is greater than mid ; update i ; Only single element left after search ; Method to compare which one is the more close . We find the closest by taking the difference between the target and both values . It assumes that val2 is greater than val1 and target lies between these two . ; Driver code
def findClosest ( arr , n , target ) : NEW_LINE INDENT if ( target <= arr [ 0 ] ) : NEW_LINE INDENT return arr [ 0 ] NEW_LINE DEDENT if ( target >= arr [ n - 1 ] ) : NEW_LINE INDENT return arr [ n - 1 ] NEW_LINE DEDENT i = 0 ; j = n ; mid = 0 NEW_LINE while ( i < j ) : NEW_LINE INDENT mid = ( i + j ) // 2 NEW_LINE if ( arr [ mid ] == target ) : NEW_LINE INDENT return arr [ mid ] NEW_LINE DEDENT if ( target < arr [ mid ] ) : NEW_LINE INDENT if ( mid > 0 and target > arr [ mid - 1 ] ) : NEW_LINE INDENT return getClosest ( arr [ mid - 1 ] , arr [ mid ] , target ) NEW_LINE DEDENT j = mid NEW_LINE DEDENT else : NEW_LINE INDENT if ( mid < n - 1 and target < arr [ mid + 1 ] ) : NEW_LINE INDENT return getClosest ( arr [ mid ] , arr [ mid + 1 ] , target ) NEW_LINE DEDENT i = mid + 1 NEW_LINE DEDENT DEDENT return arr [ mid ] NEW_LINE DEDENT def getClosest ( val1 , val2 , target ) : NEW_LINE INDENT if ( target - val1 >= val2 - target ) : NEW_LINE INDENT return val2 NEW_LINE DEDENT else : NEW_LINE INDENT return val1 NEW_LINE DEDENT DEDENT arr = [ 1 , 2 , 4 , 5 , 6 , 6 , 8 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE target = 11 NEW_LINE print ( findClosest ( arr , n , target ) ) NEW_LINE