Introducción

Veamos la implementación de un algoritmo que me gusta mucho; se trata de la búsqueda binaria. La primera vez que escuché de él fue en mi clase de Estructura de datos; ni siquiera sabía que algo así existía.

En fin, después de ello me fascinó mucho; sobre todo por la velocidad del mismo. Enseñaré cómo buscar una cadena en un arreglo usando recursividad con una búsqueda binaria, y cómo hacer lo mismo pero en un arreglo con números.

Haremos lo mismo pero usando el ciclo while; a eso se le llama búsqueda binaria en forma secuencial.

Nota: recuerda que este algoritmo requiere que el arreglo esté ordenado. Pásate por mi post para saber cómo ordenar arreglos de PHP.

Por otro lado, te recomiendo leer lo que son los argumentos que son tomados por referencia. Para redondear y calcular la mitad del arreglo usamos la función floor en PHP.

En caso de que obtengas errores de sintaxis con los corchetes es debido a la notación corta de arreglos en PHP.

Búsqueda binaria en arreglo de números usando recursividad en PHP

Me he dado a la tarea de poner todo esto en una función. Pongo aquí el código y más tarde lo explico:

See the gist on github.

Lo que hacemos es mandar todo el arreglo, y no le hacemos ninguna operación; simplemente modificamos los índices o límites inferiores y superiores.

Es importante notar que el arreglo se pasa por referencia, ahorrando copiarlo en memoria cada que la función se llama.

Para partir el arreglo simplemente modificamos los índices, cuando lo partimos hacia la izquierda tomamos desde el punto medio -1 hasta el valor que tiene la izquierda. Y cuando lo partimos hacia la derecha tomamos el punto medio + 1 hasta el valor que tiene la derecha.

Llamada a la función

Para llamarla la primera vez, le pasamos los límites inferiores y superiores del arreglo, el arreglo y la búsqueda. La izquierda es el 0, y la derecha es la longitud del arreglo  – 1 (esto es porque los arreglos empiezan a tomar las posiciones en el 0).

Aquí el ejemplo:

See the gist on github.

La salida es:

El elemento 200 está en el índice 7

Si lo que buscamos no está, se devuelve -1.

Búsqueda binaria en arreglo de números usando el ciclo while en PHP

Es lo mismo de arriba pero ahora no usamos recursividad, sino un ciclo while que se ejecutará siempre y cuando la derecha o el límite superior sea mayor o igual que la izquierda.

Igualmente está dentro de una función, pero dicha función ahora recibe únicamente el arreglo y la búsqueda, pues calcula y mueve los límites internamente.

See the gist on github.

Así de fácil es. Igualmente es una búsqueda binaria pero usando un ciclo while.

Cómo usar la función

Podemos probarlo así:

See the gist on github.

La salida es: El elemento 77 está en el índice 5

Sobre las cadenas

Aquí una pequeña nota: las cadenas se comparan de distinta manera, pues no podemos usar simples signos de comparación como con los números (aunque en JS sí). Para esto usamos la función strcmp.

El objetivo de este post es explicar la búsqueda binaria, pero recomiendo que sepas cómo funciona strcmp y he preparado un post para ello: uso de la función strcmp para comparar cadenas.

De ahí, el código es exactamente el mismo.

Búsqueda binaria en arreglo de cadenas usando recursividad

Lo mismo que hicimos para comparar números, pero ahora usando cadenas. Aquí el código igualmente en una función:

See the gist on github.

Buscar string en arreglo con búsqueda binaria

Podemos usar a la función así:

See the gist on github.

Con la salida que dice: El elemento computadora está en el índice 3

Búsqueda binaria en arreglo de cadenas con ciclo while

Usando strcmp y el ciclo while recorremos los límites, es decir, jugamos con ellos. Es lo mismo que hacemos con números pero sin usar operadores de comparación como < o >.

La función queda así:

See the gist on github.

Llamada a la función

Con este ejemplo de código podemos probarla:

See the gist on github.

Si lo ejecutamos, esta es la salida:

El elemento tarjeta está en el índice 6