Búsqueda binaria

El objetivo de ordenar un conjunto de datos es, generalmente, facilitar la búsqueda de uno o más elementos pertenecientes a un conjunto, aunque es posible realizar dicha búsqueda sin que el conjunto esté ordenado, pero esto trae como consecuencia un mayor tiempo de proceso.

Empecemos por este algoritmo de búsqueda: el algoritmo de la búsqueda binaria.

Búsqueda binaria

Un método eficiente de búsqueda que puede aplicarse a las matrices es la búsqueda binaria. Si partimos de que los elementos de la matriz están almacenados en orden ascendente, el proceso de búsqueda podría describirse en los siguientes pasos:

  1. Se selecciona el elemento del centro o aproximadamente del centro de la matriz.
  2. Si el valor a buscar no coincide con el elemento seleccionado, y es mayor que él, se continúa la búsqueda en la segunda mitad de la matriz. Si, por el contrario, el valor a buscar es menor que el valor del elemento seleccionado, la búsqueda continúa en la primera mitad de la matriz.
  3. En ambos casos, se halla de nuevo el elemento central, correspondiente al nuevo intervalo de búsqueda, repitiéndose el ciclo.
  4. El proceso se repite hasta que se encuentre el valor buscado, o bien hasta que el intervalo de búsqueda sea nulo, lo que querrá decir que el elemento buscado NO FIGURA en la matriz.

Y el código correspondiente a este algoritmo sería:

package com.gorka.algoritmia;

public class BusquedaBinaria {

public static int busquedaBin(double[] matriz, double valorBuscado) {

// Este método devuelve como resultado la posicion
// del valor. Si el valor no se localiza, devuelve -1

if (matriz.length == 0) {
return -1;
}

int mitad, inferior = 0;
int superior = matriz.length – 1;

do {
mitad = (inferior + superior) / 2;
if (valorBuscado > matriz[mitad]) {
inferior = mitad + 1;
} else {
superior = mitad – 1;
}
} while (matriz[mitad] != valorBuscado && inferior <= superior);

if (matriz[mitad] == valorBuscado) {
return mitad;
} else {
return -1;
}

}

}

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s