¿Por qué es difícil realizar una búsqueda binaria en una lista vinculada?

La idea de la búsqueda binaria es que mire el índice [math] \ lfloor {\ frac {n} {2}} \ rfloor [/ math] de su estructura de datos y compare el elemento en ese índice con su elemento objetivo. Esto guía si miras hacia la derecha o hacia la izquierda.

búsqueda booleana (List sc, int start, int end, int target) {
if (inicio> fin)
volver 🙁; //¡triste!
int middle = floor ((inicio + final) / 2;
if (sc.get (middle) == target)
volver 🙂; //¡feliz!
if (objetivo búsqueda de retorno (sc, start, middle-1, target);
más
búsqueda de retorno (sc, middle + 2, end, target);
}

En este caso,

List

Puede ser una ArrayList o LinkedList.

En una lista vinculada, encontrar el índice i toma tiempo [math] \ Theta (n) [/ math] para una lista de n elementos. Esto se debe a que no tenemos acceso aleatorio, por lo que pasar por índice lleva mucho tiempo. Por lo tanto, la búsqueda binaria ya no se ejecuta en [math] \ Theta (\ log n) [/ math] time, sino que se ejecuta en [math] \ Theta (n) [/ math] time:

(Dado que [math] T (n) = T (\ frac {n} {2}) + \ Theta (n) [/ math] tiene solución [math] \ Theta (n) [/ math] para el caso 1 o 3 del método maestro. Nunca puedo recordar qué caso es cuál.)

En una ArrayList (también conocido como vector), ir por índice lleva tiempo [math] \ Theta (1) [/ math] porque tenemos acceso aleatorio.

Espero que esto ayude.

Una lista vinculada sacrifica el acceso directo (es decir, la capacidad de ir directamente al i-ésimo elemento de una lista a bajo costo) para una inserción y eliminación más barata de elementos. Una lista de matriz hace exactamente el compromiso opuesto.

Un algoritmo de búsqueda binaria depende del acceso directo para encontrar el medio de sublistas sucesivas. Para encontrar el medio de una lista vinculada (suponiendo que la estructura mantiene un recuento total para que no tenga que recorrer la lista para encontrar la longitud de la lista) debe “visitar” la mitad de los elementos, por lo que bien podría haber buscado ellos.

Las listas vinculadas no permiten acceder a un elemento aleatorio en tiempo constante, a diferencia de una matriz. Las listas enlazadas solo permiten acceso secuencial, yendo al siguiente elemento de la lista (o también yendo al elemento anterior si la lista está doblemente vinculada). Acceder al elemento [math] k [/ math] ‘de una lista vinculada requiere pasos [math] k-1 [/ math] si comienza desde el principio o pasos [math] | jk | [/ math] si tiene el [math] j [/ math] ‘th elemento en cuestión.

La complejidad temporal de la búsqueda binaria se basa en el acceso aleatorio a cualquier elemento en tiempo constante. Con una lista vinculada no hay acceso aleatorio de tiempo constante. La complejidad del tiempo para la búsqueda binaria aumentaría de [math] O (\ log n) [/ math] con una matriz a [math] O (n \ log n) [/ math] con una lista vinculada, siendo incluso peor que un Búsqueda lineal simple.

Para realizar una búsqueda binaria en cualquier cosa, deberíamos tener información sobre su punto de inicio y su punto final para encontrar su punto medio, pero en el caso de una lista vinculada, tenemos información sobre su encabezado pero no sabemos sobre su final, así que cómo podemos encontrar el elemento medio incluso si tiene un puntero en la última posición, aún no podemos realizar una búsqueda binaria porque no podemos acceder a sus índices como lo hacemos en una matriz.