Capítulo 12 (pp. 211–246) de Computer Science I.

Temas

Ideas Clave

• La búsqueda binaria requiere datos ordenados; O(log n) vs lineal O(n).
• Compromisos de ordenamiento: selección/inserción O(n²) simples; quicksort/mergesort O(n log n).
• Los comparadores desacoplan el orden del ordenamiento — materializados como punteros a función en C, Comparator/lambdas en Java, funciones comparadoras en PHP.
• Escollos prácticos: desbordamiento aritmético en el punto medio ((lo+hi)/2), el inseguro “truco de la diferencia” en comparadores, la necesidad de un orden total y la estabilidad del ordenamiento.
• El análisis se conecta con los errores numéricos de fundamentos.

Ejemplos

Búsqueda binaria (entrada ordenada)

lo ← 0
hi ← longitud(A) - 1
mientras lo ≤ hi:
  mid ← lo + (hi - lo) / 2     // evita el desbordamiento de (lo + hi)
  si A[mid] = target: retornar mid
  si A[mid] < target: lo ← mid + 1
  si no: hi ← mid - 1
retornar -1

Ordenamiento por selección

para i desde 0 hasta n - 2:
  min ← i
  para j desde i + 1 hasta n - 1:
    si A[j] < A[min]: min ← j
  intercambiar A[i], A[min]

O(n²), pero simple y en el lugar.

En Java

static int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // evita el desbordamiento de (lo + hi)
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Para código en producción prefiere Arrays.sort / Collections.sort con un Comparator — consulta la parte de Java.

Citas

[1] Computer Science I, Cap. 12, pp. 211–246.