def binsearch(array, val):
    """
    Binary search.

    The input `array` must be sorted.
    Binary search of `val` in `array`. Returns `idx` such as `val == array[idx]`,
    returns `None` otherwise.
    """
    left, right = 0, len(array)
    while left <= right:
        mid = (left + right) // 2
        if array[mid] < val:
            left = mid + 1
        elif array[mid] > val:
            right = mid - 1
        else:
            return mid
    return None