Tema: Arreglos
Pregunta: ¿De qué manera se puede buscar un elemento en un arreglo de enteros MUY GRANDE sin que demore mucho?
Respuesta: Utilizando una búsqueda binaria ó BinarySearch.
La precondición para usar una búsqueda binaria es que el arreglo esté previamente ordenado. En los arreglos muy grandes se aconseja hacer un ordenamiento rápido y luego la búsqueda binaria.
Ejemplo recursivo:
Código PHP:
//
// array es el arreglo ordenado, value el valor a buscar, start y ending los límites
public int binarysearch(int array[], int value, int start, int ending) {
if (ending < start) {
return -1;
}
int middle = (start + ending) / 2;
if (array[middle] == value) {
return middle;
}
if (value < array[middle]) {
return binarysearch(array, value, start, (ending - 1));
} else if (value >= array[middle]) {
return binarysearch(array, value, (start + 1), ending);
}
return -1;
}
Ejemplo iterativo:
Código PHP:
//
// array es el arreglo ordenado, value el valor a buscar, start y ending los límites
public int binarysearch(int[] array, int value, int start, int ending) {
while (start < ending) {
int middle = (start + ending) / 2;
if (array[middle] == value) {
return middle;
}
if (value < array[middle]) {
ending = middle - 1;
} else if (value >= array[middle]) {
start = middle + 1;
}
}
return -1;
}
Usando los métodos de la clase Arrays:
Código PHP:
//
// array es el arreglo ordenado (byte, int, short, long, char...) y element es el elemento a buscar.
int posicion = Arrays.binarySarch(array, element);
En todos los ejemplos se devuelve la posición del elemento dentro del arreglo y si no existe devuelven un número negativo.
Have fun!