Donde se aplica la busqueda binaria?
Tabla de contenido
¿Dónde se aplica la búsqueda binaria?
Búsqueda binaria
- La búsqueda binaria es un algoritmo eficiente para encontrar un elemento en una lista ordenada de elementos.
- Una de las maneras más comunes de usar la búsqueda binaria es para encontrar un elemento en un arreglo.
¿Cuál es entonces el orden de la búsqueda lineal?
Búsqueda lineal comprueba secuencialmente cada elemento de la lista hasta que encuentra un elemento que coincide con el valor de objetivo. Si el algoritmo llega al fin de la lista sin encontrar el objetivo, la búsqueda termina insatisfactoriamente.
¿Cuáles son las reglas de la búsqueda binaria?
La búsqueda binaria funciona en arreglos ordenados. La búsqueda binaria comienza por comparar el elemento del medio del arreglo con el valor buscado. Si el valor buscado es igual al elemento del medio, su posición en el arreglo es retornada.
¿Cuál es la complejidad de la búsqueda binaria?
Complejidad del algoritmo de búsqueda binaria Cuando realizamos la búsqueda binaria, buscamos en una mitad y descartamos la otra mitad, reduciendo el tamaño del array a la mitad cada vez. Este resultado de esta recurrencia da logn , y la complejidad temporal es del orden de O(logn) .
¿Qué es un algoritmo de búsqueda?
Un algoritmo de búsqueda es un conjunto de instrucciones que están diseñadas para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.
¿Cómo funciona la búsqueda binaria?
La búsqueda binaria funciona en arreglos ordenados. La búsqueda binaria comienza por comparar el elemento del medio del arreglo con el valor buscado. Si el valor buscado es igual al elemento del medio, su posición en el arreglo es retornada.
¿Cuál es la mitad de la búsqueda binaria?
Esto nos da el primer problema: la mitad debería haber sido la posición (10,1), y no (5,1). Esto implica mas iteraciones, pues como el valor buscado es superior a la mitad (110 > 50), apenas discriminamos los primeros cuatro valores (en la búsqueda binaria, se va discriminando mitad a mitad, siendo muy eficiente).
¿Cuál es el rendimiento de la búsqueda binaria?
El rendimiento de la búsqueda binaria puede ser analizada reduciendo el algoritmo a un árbol binario de búsqueda, donde la raíz es el elemento en el medio del arreglo, el elemento en el medio de la primera parte del arreglo es el hijo izquierdo de la raíz y el elemento en el medio de la segunda parte es el hijo derecho de la raíz.
¿Qué es un árbol binario de búsqueda?
Un árbol binario de búsqueda es una estructura de datos que funciona basado en el principio de la búsqueda binaria: los valores del árbol están colocados en forma ordenada, y el recorrido del árbol es realizado usando un algoritmo muy parecido a la búsqueda binaria.