def binary_search(samples, target):
    """Binary search target in samples."""
    left = 0
    right = len(samples) - 1
    while left <= right:
        mid = (left + right) // 2
        if target < samples[mid].step:
            right = mid - 1
        elif target > samples[mid].step:
            left = mid + 1
        else:
            return mid

    # if right is -1, it is less than the first one.
    # if list is [1, 2, 4], target is 3, right will be 1, so wo will insert by 2.
    return right + 1