Búsqueda binaria
La búsqueda binaria sirve para encontrar el valor medio en una lista ordenada de números y, a partir de ahí, determinar si el valor buscado se encuentra en la parte superior o inferior de la lista.
El algoritmo se repite hasta que el valor buscado se encuentra… o no. Lo cuál querría decir que que no está en la lista.
Por cierto, puede que también lo veas nombrado como de intervalo medio o búsqueda logarítmica.
Los miembros de "Los androides Premium" escuchan contenido adicional en audio sobre este artículo... ¡y otros más de 100!
Hay que suscribirse para disfrutar de todo el contenido premium desde la web y la app, así como participar en las actividades premium: videoconferencias y canales premium en Discord.
Esto sería una implementación en Kotlin:
import kotlin.math.floor
/**
* O(log n)
*/
fun binarySearch(
array: IntArray,
number: Int,
prefix: Int = 0
): Int {
val index = floor(array.size.toFloat() / 2).toInt()
val myNumber = array[index]
val newArray: IntArray
var newPrefix = prefix
if (myNumber == number) {
return prefix + index
}
if (number > myNumber) {
newArray = array.copyOfRange(
index,
array.size
)
newPrefix += index
} else {
newArray = array.copyOfRange(
0,
index
)
}
return binarySearch(
newArray,
number,
newPrefix
)
}Y un test para comprobar su funcionamiento:
import org.junit.Assert.assertTrue
import org.junit.Test
class BinarySearchKtTest {
@Test
fun `if input is a number included within the array, then return the position`() {
val array = intArrayOf(
1,
2,
3,
4
)
assertTrue(
0 == binarySearch(
array,
1
)
)
assertTrue(
1 == binarySearch(
array,
2
)
)
assertTrue(
2 == binarySearch(
array,
3
)
)
assertTrue(
3 == binarySearch(
array,
4
)
)
}
}Ventajas
- La búsqueda binaria es más eficiente que la búsqueda secuencial porque divide la lista a la mitad cada vez que se itera sobre ella
- La búsqueda binaria funciona muy bien para listas grandes, ya que descarta una gran cantidad de elementos de una tacada
Desventajas
- La búsqueda binaria solo funciona con listas ordenadas. Si los datos no están ordenados, el algoritmo no funcionará
- Requiere que se conozca el tamaño de la lista de datos
Puntación Big O
Tiene una Big O de O(log (n)).
Conclusión
Es un algoritmo de búsqueda eficiente que puede ser utilizado para encontrar valores en una lista de datos ordenados.