PRÁCTICA 4A: REPORTE ESCRITO. EXPERIMENTOS Y ANÁLISIS DE ALGORITMOS DE BÚSQUEDA POR COMPARACIÓN.¶

PROFESOR: DR. ERIC SADIT TÉLLEZ AVILA

ESTUDIANTE: EDGAR SANTIAGO GONZALEZ MARTINEZ

Introducción¶

Esta actividad implementa y compara cinco algoritmos de búsqueda en el modelo de comparación: búsqueda binaria (acotada), B₀ (secuencial), B₁ (no acotada por doubling), B₂ (no acotada por double-doubling) y la estructura SkipList. El análisis se realiza sobre el dataset p016, p032, p064, p128, p256, p512 de la Unidad 3 y utiliza como conjunto de consultas los archivos cons1, cons2, cons3 y cons4.

Para cada pareja dataset con los de consulta se mide el número total de búsquedas ejecutadas, el promedio de comparaciones por consulta, el tiempo total acumulado y el tiempo promedio por consulta. El objetivo es contrastar la eficiencia algorítmica y el rendimiento práctico, observando cómo varían según la distribución de los datos y el patrón de consultas.

Conexión de Google Drive con Google Colab¶

Como primer procedimiento, se conecta Google Drive con Google Colab para poder acceder a los archivos almacenados en la nube.

La instrucción from google.colab import drive permite importar el módulo drive, el cual posibilita que Colab interactúe con Google Drive. El comando drive.mount('/content/drive') monta Google Drive en la carpeta /content/drive.

In [ ]:
# Cargar Google Drive
from google.colab import drive
drive.mount('/content/drive')

Mounted at /content/drive

Paqueterías usadas¶

En esta parte se prepara el entorno con os y json el cuaderno accede al sistema de archivos y carga estructuras en formato JSON que contienen listas de posteo y consultas.

numpy para manipular arreglos numéricos, mientras que itertools.chain facilita aplanar listas anidadas provenientes de distintas claves dentro de un mismo JSON.

Para medir rendimiento, time y random controla la aleatoriedad necesaria en la estructura probabilística SkipList.

Finalmente, pandas organiza los resultados en DataFrames para resumir y exportar, y matplotlib.pyplot permite generar, en celdas posteriores, las visualizaciones comparativas de comparaciones y tiempos.

In [ ]:
import os, json, numpy as np
from itertools import chain
import time, random, numpy as np, pandas as pd
import matplotlib.pyplot as plt

Extracción de archivos desde Google Drive¶

La función vec_global(path, dtype) carga un archivo JSON y extrae todos los números que encuentre. Si la raíz es un dict, concatena únicamente los valores que sean listas o tuplas; si la estructura está anidada, recorre recursivamente y rinde cada número. Convierte enteros y flotantes a int y construye un np.ndarray con el dtype indicado.

En la sección “Listas de posteo” define la ruta base RUTA_P y crea seis arreglos (p016, p032, p064, p128, p256, p512) leyendo cada JSON correspondiente. De forma análoga, en “Archivos de consultas” define RUTA_C y carga las consultas cons1–cons4. Con esto se dispone de dos grupos de datos: datasets donde se buscará y consultas que se aplicarán a cada dataset.

In [ ]:
def vec_global(path, dtype=np.int64):
    with open(path, encoding="utf-8") as f:
        d = json.load(f)
    if isinstance(d, dict):
        return np.fromiter(
            chain.from_iterable(v for v in d.values() if isinstance(v, (list, tuple))),
            dtype=dtype,
        )
    def walk(x):
        if isinstance(x, dict):
            for v in x.values(): yield from walk(v)
        elif isinstance(x, (list, tuple, set)):
            for v in x: yield from walk(v)
        elif isinstance(x, (np.integer, int)): yield int(x)
        elif isinstance(x, (np.floating, float)): yield int(x)
    return np.fromiter(walk(d), dtype=dtype)

# Listas de posteo (Unidad 3)
RUTA_P = "/content/drive/MyDrive/MCDI/3A_AdA/listas-posteo-con-perturbaciones"
p016 = vec_global(f"{RUTA_P}/listas-posteo-con-perturbaciones-p=016.json")
p032 = vec_global(f"{RUTA_P}/listas-posteo-con-perturbaciones-p=032.json")
p064 = vec_global(f"{RUTA_P}/listas-posteo-con-perturbaciones-p=064.json")
p128 = vec_global(f"{RUTA_P}/listas-posteo-con-perturbaciones-p=128.json")
p256 = vec_global(f"{RUTA_P}/listas-posteo-con-perturbaciones-p=256.json")
p512 = vec_global(f"{RUTA_P}/listas-posteo-con-perturbaciones-p=512.json")

# Archivos de consultas
RUTA_C = "/content/drive/MyDrive/MCDI/4A_AdA/Consultas-20251029"
cons1 = vec_global(f"{RUTA_C}/consultas-1-listas-posteo.json")
cons2 = vec_global(f"{RUTA_C}/consultas-2-listas-posteo.json")
cons3 = vec_global(f"{RUTA_C}/consultas-3-listas-posteo.json")
cons4 = vec_global(f"{RUTA_C}/consultas-4-listas-posteo.json")

# Vista de longuitud
for name, arr in [("p016",p016),("p032",p032),("p064",p064),("p128",p128),("p256",p256),("p512",p512),
                  ("cons1",cons1),("cons2",cons2),("cons3",cons3),("cons4",cons4)]:
    print(f"{name}: n={arr.size}")

p016: n=191852
p032: n=191852
p064: n=191852
p128: n=191852
p256: n=191852
p512: n=191852
cons1: n=10000
cons2: n=10000
cons3: n=10000
cons4: n=10000

Tras el análisis exploratorio, se comprobó que las listas de posteo (p016, p032, p064, p128, p256, p512) contienen el mismo multiconjunto de valores; solo difieren con el grado de desorden. Al ordenarlas, todas resultan idénticas.

Dado que los algoritmos de búsqueda sobre arreglos requieren datos ordenados, el “nivel de desorden” inicial no introduce diferencias en la evaluación. Por esta razon, en esta actividad se utiliza una sola lista representativa (p016) para comparar el desempeño frente a los distintos archivos de consultas.

Algoritmos de búsqueda¶

Parámetros de desempeño¶

La clase CmpCounter instrumenta el modelo de comparación: cada vez que se evalúa una relación (< o <=) mediante sus métodos lt y le, incrementa el contador interno count. De este modo, el cuaderno mide cuántas comparaciones de clave realiza un algoritmo por consulta, aislando ese costo lógico de otros costos.

La función timed cronometra la ejecución de una llamada con time.perf_counter(). Devuelve una tupla con el resultado de la función invocada y la duración en segundos, lo que permite reportar tanto el rendimiento teórico como el rendimiento práctico para cada algoritmo y conjunto de consultas.

In [ ]:
class CmpCounter:
    def __init__(self): self.count = 0
    def lt(self, a, b): self.count += 1; return a < b
    def le(self, a, b): self.count += 1; return a <= b

def timed(fn, *args, **kwargs):
    t0 = time.perf_counter()
    out = fn(*args, **kwargs)
    t1 = time.perf_counter()
    return out, (t1 - t0)

Binaria¶

Implementa la variante lower_bound de la búsqueda binaria acotada: dada un arreglo ordenado y un rango [lo, hi), mantiene ese intervalo, calcula mid = (lo + hi) // 2 y, si A[mid] < x, avanza lo = mid + 1; en caso contrario, reduce hi = mid. Al terminar (lo == hi) devuelve la posición de inserción i = min { j : A[j] ≥ x }. La instrumentación CmpCounter cuenta las comparaciones; la función retorna (posición, comparaciones). En el modelo de comparación, el costo es O(log n) (Cormen, Leiserson, Rivest, & Stein, 2009).

In [ ]:
def binary_search_lb(A, x, lo=0, hi=None, cmp=None):
    if hi is None: hi = len(A)
    if cmp is None: cmp = CmpCounter()
    while lo < hi:
        mid = (lo + hi) // 2
        if cmp.lt(A[mid], x):
            lo = mid + 1
        else:
            hi = mid
    return lo, cmp.count

B0: secuencial¶

La función search_B0 realiza una búsqueda secuencial tipo lower_bound: parte en sp y avanza mientras A[i] < x, contando comparaciones con CmpCounter, hasta detenerse en el primer índice donde A[i] ≥ x. En el modelo de comparación, su costo es lineal en la distancia recorrida desde sp (en el peor de los casos, $O(n)$), por lo que resulta ventajosa cuando la posición de inserción está cerca del punto de partida y desfavorable cuando está lejos (Knuth, 1998).

In [ ]:
def search_B0(A, x, sp=0, cmp=None):
    if cmp is None: cmp = CmpCounter()
    i, n = sp, len(A)
    while i < n and cmp.lt(A[i], x):
        i += 1
    return i, cmp.count

B1: doubling + binaria¶

La función search_B1 implementa una búsqueda no acotada por *doubling*** (exponential search). Desde sp, duplica el salto (i = 1, 2, 4, …) mientras A[sp+i] < x para acotar con rapidez un intervalo $[lo,\,hi)$ que contiene la posición de inserción; después aplica una **binaria restringida (binary_search_lb) en ese rango. El contador CmpCounter registra las comparaciones de ambas fases y la rutina devuelve (posición, comparaciones). En arreglos ordenados ascendentemente, el costo total es $O(\log p)$, con $p$ la distancia desde sp hasta la posición buscada, lo que la vuelve favorable cuando el objetivo está alejado del punto de partida (Cormen, Leiserson, Rivest, & Stein, 2009).

In [ ]:
def search_B1(A, x, sp=0):
    n = len(A)
    cmp = CmpCounter()
    i, p = 1, 0
    while sp + i < n and cmp.lt(A[sp + i], x):
        p = i
        i <<= 1
    lo, hi = sp + p, min(n, sp + i + 1)
    pos, _ = binary_search_lb(A, x, lo, hi, cmp=cmp)
    return pos, cmp.count

B2: no acotada con crecimiento doble-exponencial¶

La función search_B2 realiza una búsqueda no acotada que acota primero el rango mediante saltos doble-exponenciales (pt = 2^{2^t}: 2, 4, 16, 256, …) partiendo de sp. Mientras A[sp+pt-1] < x, incrementa t, actualiza prev y amplía el salto hasta encerrar la posición buscada en el intervalo $[lo,\,hi) = [\,sp+\texttt{prev},\ \min(n,\,sp+\texttt{pt})\,)$. Sobre ese subrango aplica luego binary_search_lb para obtener la posición de inserción (primer índice con $A[i]\ge x$). El contador CmpCounter acumula las comparaciones de ambas fases y la rutina retorna (posición, comparaciones). En arreglos ordenados, la expansión cuesta $O(\log\log p)$ pasos y la binaria $O(\log p)$ comparaciones, de modo que el costo total es $O(\log p)$, reduciendo la sobrecarga de la fase de acotamiento frente al doubling clásico cuando la clave está muy alejada de sp (Bentley & Yao, 1976).

In [ ]:
def search_B2(A, x, sp=0):
    n = len(A)
    cmp = CmpCounter()
    t, prev, pt = 0, 0, 2  # 2,4,16,256,...
    while sp + pt - 1 < n and cmp.lt(A[sp + pt - 1], x):
        prev = pt
        t += 1
        pt = 2 ** (2 ** t)
        if pt <= prev: pt = prev + 1
    lo, hi = sp + prev, min(n, sp + pt)
    pos, _ = binary_search_lb(A, x, lo, hi, cmp=cmp)
    return pos, cmp.count

SkipList¶

La implementación define una SkipList probabilística con nodos SkipNode que almacenan una key y un arreglo de punteros forward a distintos niveles. La clase SkipList mantiene un nodo cabecera (header), el nivel actual de la estructura (level) y el parámetro de probabilidad p que controla la altura esperada de los nodos (distribución geométrica). El método _rand_level genera aleatoriamente el nivel de un nuevo nodo; insert recorre de arriba hacia abajo registrando en update el último nodo visitado en cada nivel, ajusta self.level si el nuevo nodo es más alto, y enlaza el nodo en todos sus niveles, conservando duplicados como nodos separados. El método lower_bound(x) realiza una búsqueda descendente: avanza horizontalmente en cada nivel mientras la clave siguiente sea < x, desciende de nivel cuando ya no puede avanzar, y finalmente retorna la primera clave ≥ x (o None si no existe). La función auxiliar build_skiplist construye la estructura insertando todos los elementos de A. Con esta instrumentación, las comparaciones se cuentan mediante CmpCounter. En expectativa, la SkipList ofrece búsqueda e inserción en $O(\log n)$, con constantes bajas y balanceo probabilístico controlado por p (Pugh, 1990).

In [ ]:
class SkipNode:
    __slots__ = ("key", "forward")
    def __init__(self, key, level):
        self.key = key
        self.forward = [None]*(level+1)

class SkipList:
    def __init__(self, p=0.5, max_level=32, seed=12345):
        self.p = p; self.max_level = max_level
        random.seed(seed)
        self.header = SkipNode(None, max_level)
        self.level = 0
    def _rand_level(self):
        lvl = 0
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl
    def insert(self, key):
        update = [None]*(self.max_level+1)
        x = self.header
        for i in range(self.level, -1, -1):
            while x.forward[i] is not None and x.forward[i].key < key:
                x = x.forward[i]
            update[i] = x
        lvl = self._rand_level()
        if lvl > self.level:
            for i in range(self.level+1, lvl+1):
                update[i] = self.header
            self.level = lvl
        node = SkipNode(int(key), lvl)
        for i in range(lvl+1):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node
    def lower_bound(self, x, cmp=None):
        if cmp is None: cmp = CmpCounter()
        cur = self.header
        for i in range(self.level, -1, -1):
            while cur.forward[i] is not None and cmp.lt(cur.forward[i].key, x):
                cur = cur.forward[i]
        cur = cur.forward[0]
        return (cur.key if cur is not None else None), cmp.count

def build_skiplist(A, seed=12345, p=0.5, max_level=32):
    sl = SkipList(p=p, max_level=max_level, seed=seed)
    for v in A: sl.insert(int(v))
    return sl

Comparaciones¶

La función EvalAlgs evalúa, sobre un arreglo ya ordenado, el desempeño de los algoritmos de búsqueda definidos (Binaria, B0, B1, B2 y, opcionalmente, SkipList). Si use_skiplist es verdadero, construye una sola SkipList y la reutiliza en todas las consultas. Para cada algoritmo, recorre las claves de qs, mide el tiempo por consulta en segundos y acumula el número de comparaciones reportado por la instrumentación interna (CmpCounter). Con esos datos calcula tres indicadores agregados: el promedio de comparaciones por consulta (prom_comp/consul), el tiempo total en segundos (t_total_s) y el tiempo promedio por consulta en segundos (t_prom_s). El resultado se devuelve como un DataFrame ordenado por el nombre del algoritmo.

La función EvalData prepara la pareja dataset–consulta para el experimento. Primero ordena el arreglo base para garantizar la semántica de lower_bound en Binaria/B0/B1/B2; después, permite muestrear las consultas si se define sample_k. Luego delega en EvalAlgs el levantamiento de métricas y añade las columnas de contexto (dataset, consulta) antes de devolver un DataFrame con las columnas clave. En síntesis, EvalData organiza los datos y EvalAlgs computa los indicadores comparables de modelo de comparación y rendimiento práctico.

In [ ]:
def EvalAlgs(A_sorted, qs, seed=123, use_skiplist=True):
    if use_skiplist:
        sl = build_skiplist(A_sorted, seed=seed)
    algos = {
        "Binaria": lambda arr, x: binary_search_lb(arr, x),
        "B0":      lambda arr, x: search_B0(arr, x),
        "B1":      lambda arr, x: search_B1(arr, x),
        "B2":      lambda arr, x: search_B2(arr, x),
    }
    if use_skiplist:
        algos["skiplist"] = lambda arr, x: sl.lower_bound(x)

    rows = []
    for name, fn in algos.items():
        comps, times = [], []
        for x in qs:
            (pos, c), t = timed(fn, A_sorted, x)
            comps.append(c); times.append(t)
        rows.append({
            "algoritmo":        name,
            "consultas":        int(len(qs)),
            "prom_comp/consul": float(np.mean(comps)),
            "t_total_s":        float(np.sum(times)),
            "t_prom_s":         float(np.mean(times)),
        })
    return pd.DataFrame(rows).sort_values("algoritmo").reset_index(drop=True)

def EvalData(dataset_arr, consultas_arr, dataset_name="p=016", consulta_name="cons1",
             sample_k=None, seed=42, use_skiplist=True):
    rng = np.random.default_rng(seed)
    A = np.sort(dataset_arr, kind="stable")
    qs = consultas_arr
    if (sample_k is not None) and (len(qs) > sample_k):
        idx = rng.choice(len(qs), size=sample_k, replace=False)
        qs = qs[idx]

    df = EvalAlgs(A, qs, seed=seed, use_skiplist=use_skiplist)  # <— renombrada
    df.insert(0, "dataset", dataset_name)
    df.insert(1, "consulta", consulta_name)

    cols = ["dataset","consulta","algoritmo","consultas","prom_comp/consul","t_total_s","t_prom_s"]
    out = df[cols].sort_values("algoritmo").reset_index(drop=True)
    display(out)
    return out

Resultados¶

Archivo p=016 con el archivo de consulta cons1¶

Se ejecutaron 10,000 consultas (tamaño de cons1). En comparaciones promedio por consulta, el orden observado es: B1, B2, Binaria, SkipList y B0.

En tiempo, el comportamiento es consistente con la teoría: B1 y B2 usan menos comparaciones y también lideran en tiempo; SkipList queda en un nivel intermedio y Binaria es muy estable, aunque ligeramente más lenta. B0 resulta la peor opción.

In [ ]:
results_p016_cons1 = EvalData(p016, cons1, dataset_name="p=016", consulta_name="cons1", seed=42, use_skiplist=True)
dataset consulta algoritmo consultas prom_comp/consul t_total_s t_prom_s
0 p=016 cons1 B0 10000 29.5284 0.045016 0.000005
1 p=016 cons1 B1 10000 9.7896 0.023589 0.000002
2 p=016 cons1 B2 10000 10.1000 0.026562 0.000003
3 p=016 cons1 Binaria 10000 17.6297 0.036202 0.000004
4 p=016 cons1 skiplist 10000 21.9627 0.030156 0.000003

Archivo p=016 con el archivo de consulta cons2¶

En comparaciones promedio por consulta, el orden observado es: Binaria, B1, B2, SkipList y B0.

En tiempo, el patrón cambia: SkipList obtiene el mejor tiempo total, seguida de Binaria, B1 y B2. B0 queda muy por detrás. Esto refuerza que más comparaciones no siempre implican mayor tiempo: aunque SkipList compara más que Binaria, su bucle y saltos por niveles le dan mejor tiempo para las consultas.

In [ ]:
results_p016_cons2 = EvalData(p016, cons2, dataset_name="p=016", consulta_name="cons2", seed=42, use_skiplist=True)
dataset consulta algoritmo consultas prom_comp/consul t_total_s t_prom_s
0 p=016 cons2 B0 10000 503.5401 0.773648 0.000077
1 p=016 cons2 B1 10000 17.9671 0.040135 0.000004
2 p=016 cons2 B2 10000 18.5620 0.045553 0.000005
3 p=016 cons2 Binaria 10000 17.6827 0.037758 0.000004
4 p=016 cons2 skiplist 10000 25.7413 0.035895 0.000004

Archivo p=016 con el archivo de consulta cons3¶

En comparaciones promedio por consulta, el orden observado es: Binaria, B2, B1, SkipList y B0.

En tiempo, gana Binaria, seguida de B2, B1 y SkipList; B0 queda muy por detrás. Con este patrón de consultas, Binaria domina en ambas métricas; B2 supera a B1 y SkipList no aporta ventaja en tiempo.

In [ ]:
results_p016_cons3 = EvalData(p016, cons3, dataset_name="p=016", consulta_name="cons3", seed=42, use_skiplist=True)
dataset consulta algoritmo consultas prom_comp/consul t_total_s t_prom_s
0 p=016 cons3 B0 10000 7575.7269 14.020803 0.001402
1 p=016 cons3 B1 10000 25.8497 0.056442 0.000006
2 p=016 cons3 B2 10000 20.8490 0.050681 0.000005
3 p=016 cons3 Binaria 10000 17.6385 0.039188 0.000004
4 p=016 cons3 skiplist 10000 29.8543 0.057508 0.000006

Archivo p=016 con el archivo de consulta cons4¶

En comparaciones promedio por consulta, el orden observado es: Binaria, B2, B1, SkipList y B0.

En tiempo, domina Binaria, seguida de B2 y B1; SkipList queda atrás y B0 es claramente inviable. En este patrón, binaria es la mejor tanto en comparaciones como en tiempo, B2 supera a B1 y la SkipList no ofrece ventaja.

In [ ]:
results_p016_cons4 = EvalData(p016, cons4, dataset_name="p=016", consulta_name="cons4", seed=42, use_skiplist=True)
dataset consulta algoritmo consultas prom_comp/consul t_total_s t_prom_s
0 p=016 cons4 B0 10000 98816.2924 171.919109 0.017192
1 p=016 cons4 B1 10000 32.7487 0.074762 0.000007
2 p=016 cons4 B2 10000 21.6608 0.057602 0.000006
3 p=016 cons4 Binaria 10000 17.6355 0.043827 0.000004
4 p=016 cons4 skiplist 10000 33.6267 0.107717 0.000011
In [ ]:
pd_global = pd.concat([results_p016_cons1, results_p016_cons2, results_p016_cons3, results_p016_cons4],ignore_index=True)
#display(pd_global)

En los gráficos se visualizan los mismos resultados descritos en las tablas, comparando el tiempo promedio y las comparaciones promedio por consulta. Se agrupan por tipo de algoritmo para mantener la misma escala y evitar distorsiones cuando algún método consume mucho más tiempo o comparaciones.

In [36]:
def plot_results(df, value_col, suptitle, xlabel, fmt="{:.6f}"):
    algos = list(df["algoritmo"].drop_duplicates())
    fig, axes = plt.subplots(len(algos), 1, figsize=(9, 1.8*len(algos)), sharex=False)
    if len(algos) == 1:
        axes = [axes]
    for ax, algo in zip(axes, algos):
        sub = df[df["algoritmo"] == algo]
        cons_order = list(sub["consulta"].drop_duplicates())
        vals = sub.set_index("consulta")[value_col].reindex(cons_order)
        ax.barh(cons_order, vals.values)
        for i, v in enumerate(vals.values):
            if pd.notna(v):
                ax.text(v, i, f" {fmt.format(v)}", va="center", ha="left", fontsize=8)
        ax.set_title(algo)
        ax.set_ylabel("consulta")
    axes[-1].set_xlabel(xlabel)
    fig.suptitle(suptitle, y=0.995, fontsize=12)
    plt.tight_layout()
    plt.show()

# 1) Tiempo promedio (s)
plot_results(
    pd_global,
    value_col="t_prom_s",
    suptitle="Tiempo promedio por consulta (s)",
    xlabel="segundos por consulta",
    fmt="{:.6f}"
)

# 2) Comparaciones promedio por consulta
plot_results(
    pd_global,
    value_col="prom_comp/consul",
    suptitle="Comparaciones promedio por consulta",
    xlabel="comparaciones promedio",
    fmt="{:.2f}"
)

Conclusión¶

En conjunto, los resultados muestran que, con un arreglo estático y ordenado, la búsqueda binaria es el mejor punto de partida: ofrece tiempos muy bajos y estables, siendo con frecuencia la más rápida.

Las variantes no acotadas confirman la teoría: B1 y B2 crecen de forma logarítmica con la distancia a la posición objetivo; además, B2 suele superar a B1 cuando las claves están lejos gracias a una acotación más agresiva. La SkipList puede competir en tiempo e incluso ganar en ciertos patrones, aunque no reduce comparaciones frente a binaria y añade sobrecarga estructural. B0 solo es razonable si la clave está muy próxima al punto de partida; de lo contrario, su costo se dispara.

Referencias¶

Bentley, J. L., & Yao, A. C.-C. (1976). An almost optimal algorithm for unbounded searching. Information Processing Letters, 5(3), 82–87.

Bentley, J. L., & McGeoch, C. C. (1985). Amortized analyses of self-organizing sequential search heuristics. Communications of the ACM, 28(4), 404–411.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.

Knuth, D. E. (1998). The art of computer programming, Volume 3: Sorting and searching (2nd ed.). Addison-Wesley.

Pugh, W. (1990). Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668–676.

Sadit. (s. f.). 5. Algoritmos de búsqueda en el modelo de comparación. En Curso Introductorio al Análisis de Algoritmos con Julia. Recuperado de https://sadit.github.io/ALGO-IR/cap5-busqueda.html