Algoritmo O (log n) para encontrar el elemento con rango i en la unión de listas preordenadas

Question

Dadas dos listas ordenadas, cada una con n números reales, hay un algoritmo de tiempo O (log n) para calcular el elemento de rango i (donde i coresponds al índice en orden creciente) en la unión de las dos listas, suponiendo que los elementos de las dos listas son distintos?

EDITAR: @BEN: Esto es lo que he estado haciendo, pero todavía no lo entiendo.

Tengo un ejemplo;

Lista A: 1, 3, 5, 7 Lista B: 2, 4, 6, 8

Find rango (i) = 4.

Primer paso: i/2 = 2; Lista A contiene ahora es un: 1, 3 Lista B contiene ahora es B: 2, 4

  compare A[i] to B[i] i.e 

       A[i] is less; 

       So the lists now become : 

        A: 3 
        B: 2,4 

Segundo paso: i/2 = 1

  List A now contains A:3 
     List B now contains B:2 

     NoW I HAVE LOST THE VALUE 4 which is actually the result ... 

Sé que me falta algo, pero incluso después de casi un día de reflexión, no puedo imaginarlo ...

Answer 1

Sí:

Usted conoce el elemento se encuentra dentro de cualquiera índice de [0,i] de la primera lista o [0,i] de la segunda lista. Tome el elemento i/2 de cada lista y compare. Proceda por bisección.

No incluyo ningún código porque este problema se parece mucho a la tarea.

EDITAR: Bisección es el método detrás de la búsqueda binaria.Funciona así:

Supongamos que i = 10; (indexación basada en cero, estamos buscando el 11 ° elemento en general).

En el primer paso, sabrá que la respuesta está en list1 (0 ... 10) o list2 (0 ... 10). Tome a = list1 (5) y b = list2 (5).

Si a> b, entonces hay 5 elementos en list1 que vienen antes de a, y al menos 6 elementos en list2 que vienen antes de a. Entonces a es un límite superior en el resultado. Del mismo modo, hay 5 elementos en list2 que vienen antes de b y menos de 6 elementos en list1 que vienen antes de b. Entonces b es un límite inferior en el resultado. Ahora sabemos que el resultado está en la lista1 (0..5) o en la lista2 (5..10). Si es < b, entonces el resultado se encuentra en la lista1 (5..10) o en la lista2 (0..5). Y si a == b tenemos nuestra respuesta (pero el problema decía que los elementos eran distintos, por lo tanto a! = B).

Recordamos este proceso, reduciendo el tamaño del espacio de búsqueda a la mitad en cada paso. La bisección se refiere al hecho de que elegimos el elemento medio (bisectriz) fuera del rango que sabemos que incluye el resultado.

Por lo tanto, la única diferencia entre esta búsqueda y la binaria es que en la búsqueda binaria lo comparamos con un valor que estamos buscando, pero aquí lo comparamos con un valor de la otra lista.

NOTA: esto es realmente O(log i) que es mejor (al menos no peor que) que O(log n). Además, para i pequeño (quizás i < 100), en realidad serían menos operaciones para fusionar los primeros i elementos (búsqueda lineal en lugar de bisección) porque eso es mucho más simple. Cuando agrega el comportamiento del caché y la ubicación de los datos, la búsqueda lineal puede ser más rápida para i hasta varios miles.

Además, si i> n continuación, se basan en el hecho de que el resultado tiene que ser hacia el final de cualquiera de las listas, su rango inicial de candidatos en cada lista es de ((en) .. n)

Answer 2

Al fusionar dos listas, tendrá que tocar cada elemento en ambas listas. Si no tocas todos los elementos, algunos elementos quedarán atrás. Por lo tanto, su límite inferior teórico es O (n). Entonces no puedes hacerlo de esa manera.

No tiene que ordenar, ya que tiene dos listas que ya están ordenadas, y puede mantener ese orden como parte de la fusión.

Answer 3

editar: oops, He interpretado mal la pregunta. Pensé que se le había otorgado valor, que deseaba encontrar rango, y no al revés. Si usted quiere encontrar el rango de valor determinado, entonces esto es cómo hacerlo en O(log N):

sí, se puede hacer esto en O(log N), si la lista permite O(1) de acceso aleatorio (es decir, es una matriz y no una ligada lista).

• La búsqueda binaria en L1
• La búsqueda binaria en L2
• Suma de los índices

Habría que trabajar a cabo los cálculos, +1, -1, lo que hacer si el elemento no se encuentra, etc., pero esa es la idea.

Answer 4

Aquí es cómo lo haces.

Deje que la primera lista sea ListX y la segunda lista sea ListY. Necesitamos encontrar la combinación correcta de ListX[x] y ListY[y] donde x + y = i. Como x, y, i son números naturales, podemos restringir inmediatamente nuestro dominio de problema al x*y. Y al usar las ecuaciones max(x) = len(ListX) y max(y) = len(ListY) ahora tenemos un subconjunto de x*y elementos en el formulario [x, y] que debemos buscar.

Lo que usted hará es pedir los elementos como [i - max(y), max(y)], [i - max(y) + 1, max(y) - 1], ..., [max(x), i - max(x)]. A continuación, bisecará esta lista eligiendo la combinación del medio [x, y]. Como las listas están ordenadas y son distintas, puede probar ListX[x] < ListY[y]. Si es verdadero, entonces bisectamos la mitad superior de nuestras combinaciones [x, y] o si es falso, entonces bisecamos la mitad inferior. Seguirás dividiendo hasta encontrar la combinación correcta.

Hay muchos detalles que dejé, pero esa es la esencia general de la misma. De hecho, es O (log (n))!

Editar: Como Ben señaló esto realmente O(log(i)). Si dejamos n = len(ListX) + len(ListY) entonces sabemos que i <= n.