找到一个索引 k，使得对于区间 [0,l-1] 中的所有 k，max(A[k], B[k]) 在小于 O(l) 的时间内最小化

Question

我有两个长度为l的数组A和B，一个按升序排序，另一个按降序排序。我需要找到一个索引 k，使得对于区间 [0,l-1] max(A[k], B[k]) 中的所有 k 来说，max(A[k], B[k]) 是最小的。有没有办法在小于 O(l) 的时间内做到这一点？

Answer 1

因为一个数组按升序排序，另一个数组按降序排序，因此您可以利用这种排序性，通过二分搜索在

k

时间内找到最佳

log(l)

。

请参阅下面的 Python 实现：

def find_min_max_index(a: list[int], b: list[int]) -> int:
    """
    Finds the index k for which the maximum of a[k] and b[k] is minimal.

    This function assumes that list a is sorted in ascending order and list b is sorted
    in descending order. It uses a binary search approach to find the optimal index k
    efficiently.

    Args:
        a: The first list, sorted in ascending order.
        b: The second list, sorted in descending order.

    Returns:
        int: The index k such that max(a[k], b[k]) is minimal. 
             If the function cannot find such an index, it returns -1.
    """
    low, high = 0, len(a) - 1
    while low < high:
        mid = (low + high) // 2
        if max(a[mid], b[mid]) > max(a[mid + 1], b[mid + 1]):
            low = mid + 1
        else:
            high = mid
    return low

def main() -> None:
    print(f'{find_min_max_index(a=[1, 3, 5], b=[3, 2, 1]) = }')
    print(f'{find_min_max_index(a=[1, 2, 3], b=[3, 2, 1]) = }')
    print(f'{find_min_max_index(a=[2, 4, 8, 16, 32], b=[64, 48, 36, 24, 12]) = }')

if __name__ == '__main__':
    main()

输出：

find_min_max_index(a=[1, 3, 5], b=[3, 2, 1]) = 0
find_min_max_index(a=[1, 2, 3], b=[3, 2, 1]) = 1
find_min_max_index(a=[2, 4, 8, 16, 32], b=[64, 48, 36, 24, 12]) = 3