Ver Mensaje Individual
  #35 (permalink)  
Antiguo 29/04/2006, 10:29
Avatar de Tipdar
Tipdar
 
Fecha de Ingreso: octubre-2005
Mensajes: 261
Antigüedad: 9 años
Puntos: 4
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 valueint startint ending) {
        if (
ending start) {
            return -
1;
        }
        
int middle = (start ending) / 2;
        if (array[
middle] == value) {
            return 
middle;
        }
        if (
value < array[middle]) {
            return 
binarysearch(array, valuestart, (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 startint 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!
__________________
El último TipdaR