Здравствуйте,
У меня есть 2 несортированных массива A и B, оба длинной n. С помощью функции query(k) - которая предположим у меня есть, я могу найти k-наименьший элемент как массива А, так и массива B в константном времени. (К примеру A.query(5) выдасть пятое по величине число массива А). Нужно определить медиану А и B, которая является n-минимальным элементом обоих массивов, причем c O(log2 n)
Помогите, пожалуйта, с алгоритмом...Буду очень признательна!:)
Я читала уже кое-что по этой теме и мне кажется, что медина обоих массивов находится между медианами обоих массивов по отдельности. Но в общем проблемы у меня...