Listas, búsqueda binaria y procedimientos

Listas: muchos datos bajo un solo nombre

Una lista es una colección ordenada de elementos guardada bajo un solo nombre. En lugar de crear score1, score2, score3… usas una sola variable scores. Esto es abstracción de datos: tratas muchos valores como una sola cosa.

Aquí nums[1] es 4 y nums[3] es 1. Si pides una posición que no existe, como nums[5] o nums[0], el programa da error (índice fuera de rango).

Operaciones con listas

list ← [10, 20, 30]

INSERT(list, 2, 15)

REMOVE(list, 1)

Búsqueda secuencial y búsqueda binaria

Buscar un valor en una lista es una tarea muy común. Hay dos métodos.

Búsqueda secuencial (lineal): revisas el primer elemento, luego el segundo, y así hasta encontrar el valor o llegar al final. Funciona con cualquier lista. En el peor caso revisas los $n$ elementos.

Búsqueda binaria: como buscar una palabra en un diccionario: abres por la mitad y descartas la mitad que no sirve. Pero tiene una condición:

El procedimiento es:

1. Define low ← 1 y high ← LENGTH(lista).

2. Revisa el elemento del medio: posición $\lfloor (low + high)/2 \rfloor$.

3. Si es el valor buscado, terminaste.

4. Si el valor buscado es menor, descarta la mitad derecha (high pasa a ser medio − 1). Si es mayor, descarta la mitad izquierda (low pasa a ser medio + 1).

5. Repite hasta encontrarlo o hasta que no queden elementos.

¿Qué tan rápida es?

Cada revisión descarta la mitad de los elementos. Entonces el número de pasos en el peor caso es aproximadamente $\log_2 n$: la cantidad de veces que puedes partir $n$ por la mitad.

Por eso el gancho del inicio se resuelve en unos 20 pasos: $2^{20} = 1{,}048{,}576$, que es un poco más de un millón.

Procedimientos: abstracción procedimental

Un procedimiento es un grupo de instrucciones con nombre que puedes usar una y otra vez. Así no repites código y puedes usarlo sin pensar en cómo funciona por dentro. Eso es abstracción procedimental.

PROCEDURE nombre(parametro1, parametro2) {

    instrucciones

    RETURN(valor)

}

• Los parámetros son las entradas (variables que reciben datos).

• Los argumentos son los valores concretos que das al llamarlo.

• RETURN(valor) termina el procedimiento y devuelve un valor a quien lo llamó.

Los procedimientos también pueden llamarse unos dentro de otros: mystery(mystery(3, 8), 5) primero evalúa lo de adentro y usa ese resultado como argumento.

Cuidado con las listas vacías

Un procedimiento debe funcionar también con casos límite (edge cases). Si average divide entre LENGTH(list) y la lista está vacía, divide entre 0 y da error. Se arregla con un IF:

PROCEDURE average(list) {

    IF (LENGTH(list) = 0) {

        RETURN(0)

    }

    total ← 0

    FOR EACH x IN list {

        total ← total + x

    }

    RETURN(total / LENGTH(list))

}

PROCEDURE countAbove(list, limit)

{

  count ← 0

  FOR EACH item IN list

  {

    IF (item > limit)

    {

      count ← count + 1

    }

  }

  RETURN(count)

}

PROCEDURE mystery(a, b)

{

  IF (a > b)

  {

    RETURN(a)

  }

  ELSE

  {

    RETURN(b)

  }

}

PROCEDURE average(list)

{

  total ← 0

  FOR EACH x IN list

  {

    total ← total + x

  }

  RETURN(total / LENGTH(list))

}

Vuelve al principio: con una lista ordenada de 1,000,000 de nombres, la búsqueda binaria encuentra a cualquier estudiante en unos 20 pasos, en lugar de hasta un millón.

Resumen

• Una lista guarda varios elementos bajo un nombre; en AP las posiciones empiezan en 1, y un índice fuera de rango causa error.

• APPEND, INSERT, REMOVE, LENGTH y FOR EACH son las operaciones básicas; INSERT y REMOVE mueven los demás elementos.

• La búsqueda secuencial sirve con cualquier lista; la binaria exige una lista ordenada y necesita unos $\log_2 n$ pasos.

• Un procedimiento tiene parámetros (entradas) y puede devolver un valor con RETURN.

• La abstracción procedimental evita repetir código y permite arreglar o mejorar algo en un solo lugar.

• Prueba siempre los casos límite, como una lista vacía.