Búsqueda binaria

def buscar(a, x):
    """Posición de x en la lista ordenada a, o -1 si no está."""
    izq, der = 0, len(a) - 1          # x solo puede estar en a[izq..der]
    while izq <= der:
        medio = (izq + der) // 2      # en Python los enteros no se desbordan
        if a[medio] == x:
            return medio
        if a[medio] < x:
            izq = medio + 1           # x está a la derecha del medio
        else:
            der = medio - 1           # x está a la izquierda
    return -1                         # la zona se ha quedado vacía


a = [3, 8, 15, 23, 42, 57, 61, 78, 90]
print("buscar(a, 57) =", buscar(a, 57))
print("buscar(a, 4) =", buscar(a, 4), "(no está)")

/** Posición de x en el array ordenado a, o -1 si no está. */
function buscar(a, x) {
    let izq = 0, der = a.length - 1;                // x solo puede estar en a[izq..der]
    while (izq <= der) {
        const medio = Math.floor((izq + der) / 2);  // la división entera hay que hacerla a mano
        if (a[medio] === x) return medio;
        if (a[medio] < x) izq = medio + 1;          // x está a la derecha del medio
        else der = medio - 1;                       // x está a la izquierda
    }
    return -1;                                      // la zona se ha quedado vacía
}

const a = [3, 8, 15, 23, 42, 57, 61, 78, 90];
console.log(`buscar(a, 57) = ${buscar(a, 57)}`);
console.log(`buscar(a, 4) = ${buscar(a, 4)} (no está)`);

using System;

class Program {
    // Posición de x en el array ordenado a, o -1 si no está.
    static int Buscar(int[] a, int x) {
        int izq = 0, der = a.Length - 1;          // x solo puede estar en a[izq..der]
        while (izq <= der) {
            int medio = izq + (der - izq) / 2;    // así la suma no se desborda
            if (a[medio] == x) return medio;
            if (a[medio] < x) izq = medio + 1;    // x está a la derecha del medio
            else der = medio - 1;                 // x está a la izquierda
        }
        return -1;                                // la zona se ha quedado vacía
    }

    static void Main() {
        int[] a = { 3, 8, 15, 23, 42, 57, 61, 78, 90 };
        Console.WriteLine(
quot;buscar(a, 57) = {Buscar(a, 57)}");
        Console.WriteLine(
quot;buscar(a, 4) = {Buscar(a, 4)} (no está)");
    }
}

<?php
/** Posición de $x en el array ordenado $a, o -1 si no está. */
function buscar(array $a, int $x): int {
    $izq = 0;
    $der = count($a) - 1;                         // $x solo puede estar en $a[$izq..$der]
    while ($izq <= $der) {
        $medio = intdiv($izq + $der, 2);          // división entera
        if ($a[$medio] === $x) return $medio;
        if ($a[$medio] < $x) $izq = $medio + 1;   // $x está a la derecha del medio
        else $der = $medio - 1;                   // $x está a la izquierda
    }
    return -1;                                    // la zona se ha quedado vacía
}

$a = [3, 8, 15, 23, 42, 57, 61, 78, 90];
echo "buscar(a, 57) = " . buscar($a, 57) . "\n";
echo "buscar(a, 4) = " . buscar($a, 4) . " (no está)\n";

def buscar(a, x, izq, der):
    """La misma búsqueda, recursiva: cada llamada mira una zona la mitad de grande."""
    if izq > der:                                 # caso base: zona vacía
        return -1
    medio = (izq + der) // 2
    if a[medio] == x:
        return medio
    if a[medio] < x:
        return buscar(a, x, medio + 1, der)
    return buscar(a, x, izq, medio - 1)

/** La misma búsqueda, recursiva: cada llamada mira una zona la mitad de grande. */
function buscar(a, x, izq = 0, der = a.length - 1) {
    if (izq > der) return -1;                     // caso base: zona vacía
    const medio = Math.floor((izq + der) / 2);
    if (a[medio] === x) return medio;
    return a[medio] < x ? buscar(a, x, medio + 1, der)
                        : buscar(a, x, izq, medio - 1);
}

// La misma búsqueda, recursiva: cada llamada mira una zona la mitad de grande.
static int Buscar(int[] a, int x, int izq, int der) {
    if (izq > der) return -1;                     // caso base: zona vacía
    int medio = izq + (der - izq) / 2;
    if (a[medio] == x) return medio;
    return a[medio] < x ? Buscar(a, x, medio + 1, der)
                        : Buscar(a, x, izq, medio - 1);
}

/** La misma búsqueda, recursiva: cada llamada mira una zona la mitad de grande. */
function buscar(array $a, int $x, int $izq, int $der): int {
    if ($izq > $der) return -1;                   // caso base: zona vacía
    $medio = intdiv($izq + $der, 2);
    if ($a[$medio] === $x) return $medio;
    return $a[$medio] < $x ? buscar($a, $x, $medio + 1, $der)
                           : buscar($a, $x, $izq, $medio - 1);
}

def primera_mayor_o_igual(a, x):
    """Primera posición con a[i] >= x (len(a) si no hay ninguna): sirve con valores repetidos."""
    izq, der = 0, len(a)                  # ojo: aquí der es exclusivo, la zona es a[izq..der)
    while izq < der:
        medio = (izq + der) // 2
        if a[medio] < x:
            izq = medio + 1
        else:
            der = medio                   # a[medio] >= x: el medio puede ser la respuesta
    return izq                            # izq == der: la frontera


# La biblioteca estándar ya la trae: bisect.bisect_left(a, x) hace exactamente esto

/** Primera posición con a[i] >= x (a.length si no hay ninguna): sirve con valores repetidos. */
function primeraMayorOIgual(a, x) {
    let izq = 0, der = a.length;          // ojo: aquí der es exclusivo, la zona es a[izq..der)
    while (izq < der) {
        const medio = Math.floor((izq + der) / 2);
        if (a[medio] < x) izq = medio + 1;
        else der = medio;                  // a[medio] >= x: el medio puede ser la respuesta
    }
    return izq;                            // izq == der: la frontera
}

// Primera posición con a[i] >= x (a.Length si no hay ninguna): sirve con valores repetidos.
static int PrimeraMayorOIgual(int[] a, int x) {
    int izq = 0, der = a.Length;          // ojo: aquí der es exclusivo, la zona es a[izq..der)
    while (izq < der) {
        int medio = izq + (der - izq) / 2;
        if (a[medio] < x) izq = medio + 1;
        else der = medio;                  // a[medio] >= x: el medio puede ser la respuesta
    }
    return izq;                            // izq == der: la frontera
}

// Array.BinarySearch(a, x) devuelve la posición o, si no está, ~(dónde iría): con repetidos
// puede devolver cualquiera de ellos, por eso esta versión.

/** Primera posición con $a[$i] >= $x (count($a) si no hay ninguna): sirve con valores repetidos. */
function primeraMayorOIgual(array $a, int $x): int {
    $izq = 0;
    $der = count($a);                      // ojo: aquí $der es exclusivo, la zona es $a[$izq..$der)
    while ($izq < $der) {
        $medio = intdiv($izq + $der, 2);
        if ($a[$medio] < $x) $izq = $medio + 1;
        else $der = $medio;                // $a[$medio] >= $x: el medio puede ser la respuesta
    }
    return $izq;                           // $izq == $der: la frontera
}