algorithm - iterativa - busqueda binaria pdf
¿Cómo es posible hacer una búsqueda binaria en una lista de enlaces individuales en O(n) tiempo? (3)
Es absolutamente posible hacer que esto funcione. De hecho, solo hay un cambio que debe realizar en el algoritmo de lista con doble enlace para que funcione.
El problema con el caso de la lista de enlaces individuales es que si tiene un puntero al medio de la lista, no puede retroceder para volver al primer cuarto de la lista. Sin embargo, si lo piensas bien, no necesitas comenzar desde el medio para hacer esto. En su lugar, puede comenzar al principio de la lista y caminar hasta el primer trimestre. Esto toma (esencialmente) la misma cantidad de tiempo que antes: en lugar de retroceder n / 4 pasos, puede comenzar en la parte delantera y avanzar n / 4 pasos.
Ahora suponga que ha realizado el primer paso y se encuentra en la posición n / 4 o 3n / 4. En este caso, tendrá el mismo problema que antes si necesita retroceder a la posición n / 8 o la posición 5n / 8. En el caso de que necesite llegar a la posición n / 8, puede comenzar nuevamente al principio de la lista y avanzar n / 8 pasos. ¿Qué pasa con el caso 5n / 8? Aquí está el truco: si aún tiene un puntero hacia el punto n / 2, entonces puede comenzar allí y caminar hacia adelante n / 8 pasos, que lo llevarán al lugar correcto.
De manera más general, en lugar de almacenar un puntero en el medio de la lista, almacene dos punteros en la lista: uno en el frente del rango donde podría estar el valor y otro en el centro del rango donde podría estar el valor. Si necesita avanzar en la lista, actualice el puntero al comienzo del rango para que sea el puntero al centro del rango, luego mueva el puntero al centro del rango hacia adelante hasta la mitad del final del rango. Si necesita avanzar hacia atrás en la lista, actualice el puntero al centro del rango para que sea el puntero al frente del rango, luego camine hacia delante hasta la mitad.
En general, esto tiene la misma complejidad de tiempo que en el caso doblemente vinculado: damos n / 2 pasos, luego n / 4 pasos, luego n / 8 pasos, etc., que suma un total de O (n) pasos. También hacemos solo O (log n) comparaciones totales. La única diferencia es el puntero adicional que debemos seguir.
¡Espero que esto ayude!
Esta pregunta anterior habla sobre hacer una búsqueda binaria sobre una lista doblemente enlazada en O (n) tiempo. El algoritmo en esa respuesta funciona de la siguiente manera:
- Ir a la mitad de la lista para hacer la primera comparación.
- Si es igual al elemento que estamos buscando, hemos terminado.
- Si es más grande que el elemento que estamos buscando, camine hacia atrás hasta la mitad del comienzo y repita.
- Si es más pequeño que el elemento que estamos buscando, camine hacia delante hasta la mitad del comienzo y repita.
Esto funciona perfectamente bien para una lista con doble enlace porque es posible mover tanto hacia adelante como hacia atrás, pero este algoritmo no funcionaría en una lista de enlaces individuales.
¿Es posible hacer que la búsqueda binaria funcione a tiempo O (n) en una lista enlazada individualmente en lugar de una lista enlazada doblemente?
Esto se puede lograr utilizando el método de doble puntero (siempre que la lista esté ordenada) como se describe aquí en este trabajo de investigación: http://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf
La comparación toma O (1), lo que toma más tiempo es atravesar los nodos. Entonces, incluso si mantiene los punteros a n / 2, n / 4 y 3n / 4, el tiempo que le llevará encontrarlo seguirá siendo O (n).
Además, si comienzas desde la mitad y retrocedes (o avanzas), también podrías comparar en el camino, ya que toma la misma cantidad de tiempo hacer otra comparación: O (1).
Para resumir:
La ejecución de una búsqueda binaria en una lista enlazada no tiene sentido a menos que la matriz enlazada esté respaldada por una matriz (ArrayList) que permita el acceso directo a sus elementos en O (1).