Diferencia entre revisiones de «Búsqueda binaria»
Contenido eliminado Contenido añadido
m Revertidos los cambios de 187.142.119.9 a la última edición de Eduardosalg |
mSin resumen de edición |
||
Línea 1:
En [[ciencias de la computación]] y matemáticas, la '''búsqueda binaria''', también conocida como '''búsqueda de intervalo medio'''<ref>{{cite conference|last1=Willams, Jr.|first1=Louis F.|title=A modification to the half-interval search (binary search) method|conference=Proceedings of the 14th ACM Southeast Conference|date=1975|pages=95–101|doi=10.1145/503561.503582}}</ref> o '''búsqueda logarítmica''',{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Binary search"}} es un [[algoritmo de búsqueda]] que encuentra la posición de un valor en un [[arreglo ordenado|array ordenado]].{{Sfn|Cormen|Leiserson|Rivest|Stein|2009|p=39}}<ref>{{MathWorld |title=Binary Search |id=BinarySearch}}</ref> Compara el valor con el elemento en el medio del array, si no son iguales, la mitad en la cual el valor no puede estar es eliminada y la búsqueda continúa en la mitad restante hasta que el valor se encuentre.
La búsqueda binaria es computada en el peor de los casos en un tiempo logarítmico, realizando <math>O\bigl(\log n\bigr)</math> comparaciones, donde n es el número de elementos del
Aunque la idea es simple, implementar la búsqueda binaria correctamente requiere atención a algunos detalles como su condición de parada y el cálculo del punto medio de un intervalo.
|