Búsqueda Binaria
Páginas: 5 (1131 palabras)
Publicado: 8 de diciembre de 2012
Búsqueda binaria
La búsqueda binaria consiste en localizar el término buscado comparándolo con la mediana del conjunto de elementos previamente ordenados, reduciendo así sucesivamente el intervalo de búsqueda.
Ejemplo, dado el siguiente vector:
1 | 3 | 5 | 9 | 11 | 12 | 20 | 22 | 30 | 32 | 33 | 35 | 57 |
Suponiendo que buscamos el 5, efectuaremos los siguientes pasos:
1. Determinamos lamediana entre todos los elementos, en este caso el 20
2. nos preguntamos si 5 menor igual a 20
3. como 5 es menor que 20 reducimos el intervalo de búsqueda a los 6 primeros números
4. determinamos la nueva mediana, en este caso 9
5. nos preguntamos si 5 menor igual a 9
6. como 5 es menor que 9 reducimos el intervalo de búsqueda a los 3 primeros números
7. determinamos lanueva mediana, en este caso 3
8. nos preguntamos si 5 menor igual a 3
9. como 5 no es menor que 3 reducimos el intervalo de búsqueda a los números mayores que 3 y menores que 9, en este caso abarcamos un intervalo de un elemento, que el es 5
10. determinamos la nueva mediana de este intervalo, en este caso 5
11. nos preguntamos si 5 menor igual a 5
12. como 5 es igual a 5, hemosterminado nuestra búsqueda
A continuación se muestra el diagrama de flujo de Búsqueda Binaria suponiendo que buscamos el valor Valor dentro del arreglo X[ ]:
El algoritmo de búsqueda binaria es un excelente método para buscar datos dentro de una estructura (generalmente un arreglo unidimensional). Se le da el nombre de búsqueda binaria por que el algoritmo divide en dos el arreglo, aludiendo alconcepto de bit, el cual puede tener dos estados.
* Los datos deben estar contenido en un estructura de datos tipo vector
* Los datos del vector deben estar ordenados
La búsqueda seuencial se aplica a cualquier lista. Si la lista está ordenada, la búsqueda binaria proporciona una técnica de búsqueda mejorada. Una búsqueda binaria típica es la búsqueda de una palabra en undiccionario. Dada la palabra, se abre el libro cerca del principio, del centro o del final dependiendo de la primera letra de la palabra que busca. Se puede tener suerte y acertar con la página correcta pero, normalmente, no será así y el lector se mueve a la página anterior o posterior del libro. Por ejemplo, si la palabra comienza con la “J” y se está en la “L” se mueve uno hacia atrás. El proceso continúahasta que se encuentra la página buscada o hasta que se descubre que la palabra no está en la lista.
Una idea similar se aplica en la búsqueda en una lista ordenada. Se sitúa la lectura en el centro de la lista y se comprueba si nuestra clave coincide con el valor del elemento central. Si no se encuentra el valor de la clave, se sitúa uno en la mitad inferior o superior del elemento central dela lista. En general, si los datos de la lista están ordenados, se puede utilizar esa información para acortar el tiempo de búsqueda.
Ejemplo; se desea averiguar si el elemento 225 se encuentra en el conjunto de datos siguiente:
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
13 44 75 100 120 275 325 510
El punto central de la lista es el elemento a[3] (100). El valor que se busca es 225 quees mayor que 100; por consiguiente, la búsqueda continúa en la mitad superior del conjunto de datos de la lista, es decir, en la sublista.
a[4] a[5] a[6] a[7]
120 275 325 510
Ahora el elemento en la mitad de esta sublista a[5] (275). El valor buscado, 225, es menor que 275 y, por consiguiente, la búsqueda continúa en la mitad inferior del conjunto de datos de la lista actual, es decir, enla sublista de un único elemento:
a[4]
120
El elemento central de esta sublista es el propio elemento a[4] (120). Al ser 225 mayor que 120 la búsqueda debe continuar en una sublista vacía. Se concluye indicando que no se ha encontrado la clave en la lista.
Algoritmo y codificación de la búsqueda binaria
Suponiendo que la lista este almacenada como un array, donde los índices de la...
La búsqueda binaria consiste en localizar el término buscado comparándolo con la mediana del conjunto de elementos previamente ordenados, reduciendo así sucesivamente el intervalo de búsqueda.
Ejemplo, dado el siguiente vector:
1 | 3 | 5 | 9 | 11 | 12 | 20 | 22 | 30 | 32 | 33 | 35 | 57 |
Suponiendo que buscamos el 5, efectuaremos los siguientes pasos:
1. Determinamos lamediana entre todos los elementos, en este caso el 20
2. nos preguntamos si 5 menor igual a 20
3. como 5 es menor que 20 reducimos el intervalo de búsqueda a los 6 primeros números
4. determinamos la nueva mediana, en este caso 9
5. nos preguntamos si 5 menor igual a 9
6. como 5 es menor que 9 reducimos el intervalo de búsqueda a los 3 primeros números
7. determinamos lanueva mediana, en este caso 3
8. nos preguntamos si 5 menor igual a 3
9. como 5 no es menor que 3 reducimos el intervalo de búsqueda a los números mayores que 3 y menores que 9, en este caso abarcamos un intervalo de un elemento, que el es 5
10. determinamos la nueva mediana de este intervalo, en este caso 5
11. nos preguntamos si 5 menor igual a 5
12. como 5 es igual a 5, hemosterminado nuestra búsqueda
A continuación se muestra el diagrama de flujo de Búsqueda Binaria suponiendo que buscamos el valor Valor dentro del arreglo X[ ]:
El algoritmo de búsqueda binaria es un excelente método para buscar datos dentro de una estructura (generalmente un arreglo unidimensional). Se le da el nombre de búsqueda binaria por que el algoritmo divide en dos el arreglo, aludiendo alconcepto de bit, el cual puede tener dos estados.
* Los datos deben estar contenido en un estructura de datos tipo vector
* Los datos del vector deben estar ordenados
La búsqueda seuencial se aplica a cualquier lista. Si la lista está ordenada, la búsqueda binaria proporciona una técnica de búsqueda mejorada. Una búsqueda binaria típica es la búsqueda de una palabra en undiccionario. Dada la palabra, se abre el libro cerca del principio, del centro o del final dependiendo de la primera letra de la palabra que busca. Se puede tener suerte y acertar con la página correcta pero, normalmente, no será así y el lector se mueve a la página anterior o posterior del libro. Por ejemplo, si la palabra comienza con la “J” y se está en la “L” se mueve uno hacia atrás. El proceso continúahasta que se encuentra la página buscada o hasta que se descubre que la palabra no está en la lista.
Una idea similar se aplica en la búsqueda en una lista ordenada. Se sitúa la lectura en el centro de la lista y se comprueba si nuestra clave coincide con el valor del elemento central. Si no se encuentra el valor de la clave, se sitúa uno en la mitad inferior o superior del elemento central dela lista. En general, si los datos de la lista están ordenados, se puede utilizar esa información para acortar el tiempo de búsqueda.
Ejemplo; se desea averiguar si el elemento 225 se encuentra en el conjunto de datos siguiente:
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
13 44 75 100 120 275 325 510
El punto central de la lista es el elemento a[3] (100). El valor que se busca es 225 quees mayor que 100; por consiguiente, la búsqueda continúa en la mitad superior del conjunto de datos de la lista, es decir, en la sublista.
a[4] a[5] a[6] a[7]
120 275 325 510
Ahora el elemento en la mitad de esta sublista a[5] (275). El valor buscado, 225, es menor que 275 y, por consiguiente, la búsqueda continúa en la mitad inferior del conjunto de datos de la lista actual, es decir, enla sublista de un único elemento:
a[4]
120
El elemento central de esta sublista es el propio elemento a[4] (120). Al ser 225 mayor que 120 la búsqueda debe continuar en una sublista vacía. Se concluye indicando que no se ha encontrado la clave en la lista.
Algoritmo y codificación de la búsqueda binaria
Suponiendo que la lista este almacenada como un array, donde los índices de la...
Leer documento completo
Regístrate para leer el documento completo.