El premio de tenerlo ordenado

En una lista ordenada, cada pregunta descarta la mitad.

1Por qué

Ordenar cuesta. La lección anterior lo midió: cuadrático, y creciendo. Así que la pregunta justa es qué se gana a cambio.

Buscar en una lista desordenada es mirarlas todas: con mil datos, mil pasos, y no hay forma de saltarse ninguno. Pero si está ordenada, se puede hacer algo que sin orden sería imposible: mirar el del medio.

Si el del medio es el que buscas, listo. Si es menor, lo que buscas está a la derecha y la mitad izquierda entera deja de importar. Si es mayor, al revés. Cada pregunta parte el problema por la mitad.

Mil datos se resuelven en diez pasos. Un millón, en veinte. Es exactamente lo mismo que hace el árbol de la lección 20 — la misma idea, sobre un arreglo en vez de sobre nodos — y por eso las dos estructuras aparecen juntas en todos los ramos.

Esto es lo que compra el ordenamiento: se paga una vez, y después cada búsqueda sale casi gratis. Si vas a buscar una sola vez, no compensa; si vas a buscar mil veces, no hay comparación.

2Míralo andar

Este programa funciona. Léelo, y después ejecútalo sin cambiar nada.

#include <stdio.h>
 
int buscar(int v[], int n, int x)
{
    int izq = 0;
    int der = n - 1;
    int pasos = 0;
 
    while (izq <= der)
    {
        pasos = pasos + 1;
        int medio = (izq + der) / 2;
 
        if (v[medio] == x) return pasos;
 
        if (v[medio] < x)
            izq = medio + 1;
        else
            der = medio - 1;
    }
 
    return -1;
}
 
int main(void)
{
    int v[8] = {1, 3, 5, 7, 9, 11, 13, 15};
 
    printf("%d\n", buscar(v, 8, 13));
    return 0;
}

línea 9
Mientras quede trozo por mirar. Cuando izq pasa a der, no queda nada y no está.
línea 16
Aquí se tira media lista. Si el del medio es menor, lo que buscas no puede estar a la izquierda.
línea 28
Ocho datos, y lo encuentra en tres pasos. Con dieciséis serían cuatro.

3Ahora tú

A esta búsqueda le falta descartar la mitad izquierda. Escribe esa línea, para que encuentre el 13 en 3 pasos

#include <stdio.h>
 
int buscar(int v[], int n, int x)
{
    int izq = 0;
    int der = n - 1;
    int pasos = 0;
 
    while (izq <= der)
    {
        pasos = pasos + 1;
        int medio = (izq + der) / 2;
 
        if (v[medio] == x) return pasos;
 
        if (v[medio] < x)
            
        else
            der = medio - 1;
    }
 
    return -1;
}
 
int main(void)
{
    int v[8] = {1, 3, 5, 7, 9, 11, 13, 15};
 
    printf("%d\n", buscar(v, 8, 13));
    return 0;
}

↖︎ Tu línea va aquí. Fíjate en la de abajo: la tuya es su espejo por el otro lado.

El premio de tenerlo ordenado

1Por qué

2Míralo andar

3Ahora tú

Ejecutar

Lo que dice tu programa

Qué pasó

4Qué guarda tu programa

La pila