Así es como pensé esto. Como se trata de un problema educativo, le sugiero que deje de leer si alguno de los puntos le hace pensar: "Ajá, no había pensado en eso, puedo pensar más en esas líneas solo".
1) La misma observación que sdcwc: con una posible pequeña objeción sobre si comienza en 0 o 1, la base de datos se puede considerar como una matriz ordenada. Pido el elemento 0, obtengo el más pequeño. Pido 12, obtengo el 13 ° más pequeño. Y así. Encuentro esto más fácil de visualizar.
2) Sabemos que estamos buscando un algoritmo O (log n). Eso significa que en términos generales estamos buscando una de dos cosas:
O nos comienza a cabo mediante el cálculo del elemento más pequeño, y luego calcular el segundo más pequeño, más pequeño cuarto, octavo, etc., hasta que estemos arriba al tamaño que queremos, cada paso en tiempo constante. Esto no me parece prometedor.
O comenzamos con un problema de tamaño n luego realizamos algunas operaciones de tiempo constante que nos permiten resolver el problema original resolviendo un problema de tamaño n/2.Obviamente, podemos resolver el problema para n = 1 en tiempo constante, para completar el algoritmo. Esto suena un poco más plausible.
En realidad, no necesariamente tiene que ser n/2 cada vez. Podría ser n/3, o 999 * n/1000, y el resultado seguirá siendo O (log n). Pero no hay nada de malo en buscar n/2 primero.
3) ¿Cómo vamos a reducir el problema de esa manera? Bueno, si podemos descontar/eliminar m elementos del inicio de una matriz u otra como más pequeños que la k-ésima más pequeña, entonces podemos encontrar el (km) el elemento más pequeño del par resultante de matrices, y será el la quinta más pequeña de las matrices originales.
4) Finalmente, la observación de avance es que si el m-ésimo elemento más pequeño de la matriz A es más pequeño que el m-ésimo elemento más pequeño de la matriz B, entonces ese m-ésimo elemento de A no puede ser el (2m) el elemento más pequeño de la dos arreglos combinados. Es más pequeño que eso (o de igual valor: no estoy seguro de si "no hay repeticiones" significa "no hay repeticiones en cada base de datos", o "no hay repeticiones entre las bases de datos combinadas"), ya que hay como máximo 2 * (m- 1) elementos estrictamente más pequeños que en ambas matrices combinadas.
A menos que haya cometido un error, el resto es la codificación. Con un pequeño argumento adicional para explicar el fuera de-1 cuando k es impar, esta solución es en realidad O (log k), que es O (log n) ya que k < = 2 * n.
muy bien explicado – user2290820