busqueda binaria



Índice


Resumen ejecutivo
Con el objeto de entender el concepto y el funcionamiento en la práctica de búsqueda binaria, nos dimos la tarea de realizar las investigaciones pertinentes en lo que a búsqueda binaria se refiere; determinando las ventajas y desventajas al usar el algoritmo de este método de búsqueda.
Cuando se habla de búsqueda en memoria primaria, donde los accesos sonmucho más rápidos, se han desarrollado algoritmos que garantizan el encontrar registros ágilmente. Tal es el caso de la búsqueda binaria cuyo tiempo de búsqueda es de o(log2 n.).
El algoritmo de búsqueda binaria se basa en la metodología “divide y vencerás”, de manera que dado un arreglo de registros “ordenados” podemos buscar rápidamente alguno partiendo el arreglo a la mitad y viendo en que mitadpodría estar dicho registro, y a su vez esa mitad es dividida en dos y así sucesivamente hasta encontrar el registro.

La búsqueda binaria requiere de uno o dos accesos para encontrar en el archivo:
Para archivos grandes, ejemplo: 1,000 registros el promedio de accesos es de 9.5 y para uno de 100,000 sería de 16.
Recordemos que nuestra meta cuando hablamos de archivos es tratar de ir lomenos posible al disco.




Introducción
La presente investigación tiene como objetivo comprender la parte abstracta de la búsqueda binaria, mostrando los procedimientos en código fuente y el funcionamiento con una interfaz de usuario comprensible al resultado de una búsqueda binaria en ficheros.
Cabe señalar que esta búsqueda hasta el momento se dice que es la más eficiente, pero en lo quealgoritmo se refiere nada se queda hasta allí; ya que el objetivo siempre será buscar la eficiencia y eficacia en el funcionamiento de estos.






Objetivo de la investigación.
El lector será capaz de comprender de una manera sencilla el concepto de forma teórica y la parte practica explicada, a través de un ejemplo en el lenguaje de programación c++.




Planteamiento delproblema a investigar
Se denomina búsqueda binaria a la división de un arreglo, cuantas veces sea necesario para encontrar el objetivo buscado.
Debido a la necesidad de resolver operaciones con archivos, como ser búsquedas que sean capaces de lograr los objetivos a realizar, comprendemos que resulta interesante el manejo de la información en lo que se refiere la manipulación de ficheros.
Debemostener por entendido que existe información sobre la eficiencia y eficacia de la búsqueda binaria en ficheros, pero también existen similares que nos dejan ver las ventajas al momento de utilizarlas como ser: búsquedas indexadas secuenciales y búsquedas hash.





Justificación de la Investigación.
La razón de nuestra investigación es porque hemos ignorado en muchas maneras al momento deutilizar interfaces; realizando operaciones con comandos que contienen algoritmos que realizan búsquedas para poder cumplir su propósito, pero que desconocemos como se realiza dicha tarea internamente, porque solo las utilizamos como usuario y no las entendemos como programadores.





Metodología de Investigación.
Nuestra metodología de investigación es aquella que parte de datos generalesaceptados como validos para llegar a una conclusión de tipo particular, nombrada como deductiva.

Marco teórico de la investigación.
Búsqueda binaria
Se utiliza cuando el vector en el que queremos determinar la existencia o no de un elemento está ordenado, o puede estarlo, este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente con el número deiteraciones.
Este algoritmo está altamente recomendado para buscar en arrays enormes: En uno de 50.000.000 elementos, tarda 26 iteraciones en ejecutarse, suponiendo que la búsqueda falla, sino, siempre tarda menos en buscarlo.
Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central), si el valor de éste es mayor que el del...