Code it · Write it
Write binary search
Write binary_search(arr, target) (Python) or binarySearch(arr, target) (JavaScript/TypeScript). arr is sorted, smallest first. Return an index where arr[index] equals target, or -1 if it isn’t there.
Keep a window lo..hi that must contain the target if it is anywhere. Look at the middle: if it is the target you are done; otherwise throw away the half that can’t hold it.
def binary_search(arr, target):
# arr is sorted. Return the index of target, or -1.
# Halve the window lo..hi until you find it or it is empty.
return -1