Búsqueda binaria
Uno de los algoritmos de búsqueda más eficiente que existe en la estructura de datos es la búsqueda binaria, las características para poder implementar este algoritmo son las siguientes:
- Los datos deben estar contenido en un estructura de datos tipo vector
- Los datos del vector deben estar ordenados
Una vez que se cuenten son las características descritas, se divide el vector para poder conocer la posición central y se verifica si es el dato que se esta buscando (lineas 9-12), si es el dato que se busca regresa la posición (índice del vector), en caso de que no sea el dato que buscamos se verifica si es mayor o menor que la posición central y se vuelve a redefinir la posición final o inicial según cumpla la condición (lineas 14-18).
Debido a que el vector se encuentra ordenado si el dato que buscamos es mayor a la posición central se descartan todos los datos que se encuentren en la parte inferior, de la misma manera si el dato que buscamos en menor que la posición central definida se descarta la parte superior del vector.
Una vez que encuentre el dato el método regresara la posición en que lo encontró (linea 12), en caso de no encontrar el dato en el vector regresara el valor -1
Debido a que el vector se encuentra ordenado si el dato que buscamos es mayor a la posición central se descartan todos los datos que se encuentren en la parte inferior, de la misma manera si el dato que buscamos en menor que la posición central definida se descarta la parte superior del vector.
Una vez que encuentre el dato el método regresara la posición en que lo encontró (linea 12), en caso de no encontrar el dato en el vector regresara el valor -1
Referencia
http://www.ingenieriasw.com/busquedabinaria
Y otros 3.
ResponderEliminar