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.

 

¿Quieres ESCUCHAR este contenido en AUDIO y con algún tip adicional?

Suscribirme

Suscríbete para disfrutar de todo el contenido premium desde la web y la app, así como participar en las actividades 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.

16.11.2022

Historias androides

Recibe inspiración por email.

Además, al apuntarte te llegará un link al AUDIO DE 54 MINUTOS con mi estrategia para convertirte en un Desarrollador Android Senior.

Acepto que trates mis datos con privacidad.