Búsqueda binaria

Lea esto en otros idiomas: English Português brasileiro.

En informática, la búsqueda binaria, también conocida como búsqueda de medio intervalo búsqueda, búsqueda logarítmica, o corte binario, es un algoritmo de búsqueda que encuentra la posición de un valor objetivo dentro de una matriz ordenada. La búsqueda binaria compara el valor objetivo con el elemento central de la matriz; si son desiguales, se elimina la mitad en la que la mitad en la que no puede estar el objetivo se elimina y la búsqueda continúa en la mitad restante hasta que tenga éxito. Si la búsqueda termina con la mitad restante vacía, el objetivo no está en la matriz.

Complejidad

Complejidad de tiempo: O(log(n)) - ya que dividimos el área de búsqueda en dos para cada siguiente iteración.

Referencias

• Wikipedia
• YouTube