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.

Este contenido está restringido.
Adquiere alguna formación.
O suscríbete para difrutar de los audios y vídeos exclusivos de Los androides Premium.

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