对于一个排好序的数组A,如果我们要查找第k小的元素,很简单,只需要访问A[k-1]即可,该操作的时间复杂度是O(1).假设给你两个已经排好序的数组A和B,他们的长度分别是m和n, 如果把A和B合并成一个排序数组C, 数组C含有m+n个元素,要求设计一个算法,在lg(k)的时间内,找出数组C中第k小的元素。
例如给定数组:
A = {1, 3, 5, 7, 9}, B={2, 4, 6, 8, 10} , 合并后的数组 C = {1,2,3,4,5,6,7,8,9,10}
如果k = 7, 那么返回的元素是7