¿Qué es mejor para la búsqueda binaria, la matriz ordenada o la lista vinculada?

La búsqueda binaria es un algoritmo para el problema de búsqueda, y se puede utilizar en muchos entornos diferentes, incluidos ciertos tipos de procedimientos de decisión para problemas de optimización.

La búsqueda binaria requiere que los datos de entrada mantengan un orden parcial (en términos simples, se ordenan en orden no decreciente). El beneficio que queremos obtener del algoritmo es acceder a cada valor en la posición intermedia en tiempo constante. En una lista vinculada, obtener la posición intermedia puede llevar tiempo [matemático] O (n) [/ matemático]. Entonces, la complejidad del tiempo iría de [math] O (\ log {n}) [/ math] a [math] O (n \ log {n}) [/ math].

Una estructura de datos como una matriz es mucho más adecuada, ya que puede acceder a cualquier miembro de la matriz en tiempo constante. Recuerde que los datos deben ordenarse para usar la búsqueda binaria.

AlgoritmosBúsqueda binariaEstructuras de datosListas vinculadasProgramación informática

¿Cómo combina ACM ICPC invertir en diversidad y mantener alta la barra de entrada?

Cómo maximizar la suma de las diferencias absolutas en los índices correspondientes de dos matrices sobre todas sus permutaciones posibles

Cómo elegir un elemento único de una lista dentro de un bucle en R

¿Deben las clases de algoritmos incluir tareas de programación?

¿De dónde debería comenzar a aprender el algoritmo? ¿Debería unirme a uno de los MOOC disponibles o leer libros como ‘Introducción a los algoritmos’?

¿Qué campos del derecho no se pueden automatizar?

En una búsqueda binaria, comienza mirando la posición media de su conjunto de datos ordenado. Si el conjunto se almacena como una lista vinculada, llegar al medio es O (n) donde n es el número de elementos de datos. Por lo tanto, la búsqueda binaria en una lista vinculada ya es, en una comparación, tan grande como una búsqueda lineal. Por lo tanto, no hay razón para hacer una búsqueda binaria en una lista vinculada.

Sin embargo, supongamos que en lugar de tener un puntero al primer elemento de la lista vinculada, tenemos un puntero al elemento del medio. Entonces llegar al elemento del medio es O (1). el siguiente elemento de la lista vinculada que necesitamos es 1/4 o 3/4 del camino a través de la lista, dependiendo de si el objetivo que estamos buscando es menor o mayor que el elemento de la lista central. Entonces, tengamos dos punteros desde el elemento del medio, a la posición 1/4 y 3/4. Y dos punteros desde la posición 1/4 a la posición 1/8 y 3/8, y de manera similar desde la posición 3/4, y en general dos punteros desde cada posición. ¡Esto nos da un árbol de búsqueda binario!

Daniel R. Page

La búsqueda binaria se realiza en una matriz ordenada. Incluso si se trata de una lista vinculada, los datos deben estar ordenados o, de lo contrario, la búsqueda binaria no es posible porque seguimos reduciendo el número de elementos en los que se busca el número. Si la lista vinculada no está ordenada, solo es posible la búsqueda lineal.