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.
Este contenido está restringido.
HAZTE PREMIUM
para difrutar de los audios y vídeos exclusivos.
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.