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 disfrutar de los vídeos y audios 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.
Si quieres aprender android, te recomiendo este curso de kotlin.