binary_search.py

binary_search.py

def binarySearch(arr, x):
    maxIndex = len(arr) - 1
    low = 0
    high = maxIndex
    mid = 0

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x: low = mid + 1
        elif arr[mid] > x: high = mid - 1
        else: return mid
    
    midDiff = abs(x - arr[mid])
    if mid > 0:
        subDiff = abs(x - arr[mid-1])
        if subDiff < midDiff: return mid - 1
    if mid < maxIndex:
        addDiff = abs(x - arr[mid+1])
        if addDiff < midDiff: return mid + 1
    return mid