Búsqueda binaria
busqueda binaria

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!

Suena muy bien

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.

Publicado: 2022-11-16 Actualizado: 2023-09-14