Задача
Написати функцію яка приймає два відсортовані масиви цілих чисел з унікальними значеннями і знайти k-тий по порядку елемент.
Зробити це треба швидше ніж за лінійний час.
Рішення
Якщо просто мати по індексу на масив і пересувати їх на найменший елемент то усього нам знадобиться k ітерацій.
Так само якщо ми спробуємо злити масиви то не вдасться зробити це швидше ніж за лінійнипй час.
Якщо ж скористатися бінарним пошуком то загальна складність становитиме O(lg M + lg N), де M та N розміри вхідних масивів.
Робимо ми це так:
- будуємо індекси i та j такі що i + j == k – 1. Наприклад ділимо відрізки навпіл.
- якщо B[j-1] < A[i] < B[j] то A[j] є результатом пошуку
- якщо A[i-1] < B[j] < A[i] то результатом буде B[j]
- модифікуємо індекси таким чином:
- якщо A[i] < B[j] то:
- якщо B[j] є останнім елементом у масиві то значення яке ми шукаємо знаходиться в A
- інакше пересуваємо j на половину масиву вліво, і рівно на стільки ж позицій пересуваємо i (для того щоб їх сума дорівнювала k)
- Робимо схожі перевірки:
- якщо A[i] є останнім елементом у масиві то значення яке ми шукаємо знаходиться в B
- інакше пересуваємо i на половину масиву вліво, і рівно на стільки ж позицій пересуваємо j
- якщо A[i] < B[j] то:
- повертаємося до кроку 2.
Код на gist: