import datetime
 
def find_close(arr, e):
    start_time = datetime.datetime.now()
    
    size = len(arr)
    idx = 0
    val = abs(e - arr[idx])
 
    for i in range(1, size):
        val1 = abs(e - arr[i])
        if val1 < val:
            idx = i
            val = val1
 
    use_time = datetime.datetime.now() - start_time
 
    return arr[idx], use_time.seconds * 1000 + use_time.microseconds / 1000
 
def find_close_fast(arr, e):
    start_time = datetime.datetime.now()
        
    low = 0
    high = len(arr) - 1
    idx = -1
 
    while low <= high:
        mid = int((low + high) / 2)
        if e == arr[mid] or mid == low:
            idx = mid
            break
        elif e > arr[mid]:
            low = mid
        elif e < arr[mid]:
            high = mid
 
    if idx + 1 < len(arr) and abs(e - arr[idx]) > abs(e - arr[idx + 1]):
        idx += 1
        
    use_time = datetime.datetime.now() - start_time
 
    return arr[idx], use_time.seconds * 1000 + use_time.microseconds / 1000
 
if __name__ == "__main__":
    arr = []
    
    f = open("1Mints.txt")
    for line in f:
        arr.append(int(line))
    f.close()
    
    arr.sort()
 
    while 1:
        e = int(input("input a number:"))
        print("find_close ", find_close(arr, e))
        print ("find_close_fast ", find_close_fast(arr, e))