Skip to content
ExamplesEspañolWorkspace →

Binary Search

Finds a value in a sorted array by halving the range every step.

Level
Intermediate
Topic:
Sorting & searching
Concepts:
Input & output
Arrays
Mientras
Si
Randomness
SubProcesos
Open in Codoritmo

Run, change and debug this example in your browser.

What you'll learn

Because the list is sorted, looking at the middle element tells you which half the target can be in, and you discard the other. Every step halves the range, so 10 comparisons are enough for 512 elements: O(log n), versus O(n) for checking one by one.

Code

binary-search.psc · 53 lines
// Muestra el arreglo completo solo si es corto (30 o menos)SubProceso MostrarDatos(titulo, datos, n)    Definir i Como Entero    Si n <= 30 Entonces        Escribir Sin Saltar titulo        Para i <- 1 Hasta n Hacer            Escribir Sin Saltar datos[i], " "        FinPara        Escribir ""    SiNo        Escribir titulo, n, " números (el primero es ", datos[1], " y el último ", datos[n], ")"    FinSiFinSubProcesoAlgoritmo BusquedaBinaria    Definir datos, n, i, buscado, izquierda, derecha, medio, posicion, pasos Como Entero    Escribir "¿Cuántos números tiene la lista? (1 a 512)"    Leer n    // La búsqueda binaria necesita datos ordenados: usamos los pares 2, 4, 6...    Dimension datos[n]    Para i <- 1 Hasta n Hacer        datos[i] <- 2 * i    FinPara    MostrarDatos("Lista: ", datos, n)    // Un número al azar entre 1 y 2n: si es impar, no estará en la lista    buscado <- Aleatorio(1, 2 * n)    Escribir "Buscando el ", buscado    izquierda <- 1    derecha <- n    posicion <- 0    pasos <- 0    Mientras izquierda <= derecha Y posicion = 0 Hacer        medio <- Trunc((izquierda + derecha) / 2)        pasos <- pasos + 1        Escribir "  Paso ", pasos, ": miro la posición ", medio, " (", datos[medio], ")"        Si datos[medio] = buscado Entonces            posicion <- medio        SiNo            // Descartamos la mitad donde seguro no está            Si datos[medio] < buscado Entonces                izquierda <- medio + 1            SiNo                derecha <- medio - 1            FinSi        FinSi    FinMientras    Si posicion > 0 Entonces        Escribir "Encontrado: el ", buscado, " está en la posición ", posicion, "."    SiNo        Escribir "El ", buscado, " no está en la lista."    FinSi    Escribir "Comparaciones: ", pasos, " de ", n, " elementos."FinAlgoritmo

Flowchart

Each block in the flowchart matches one instruction in the code.

Algoritmo BusquedaBinaria
Algoritmo BusquedaBinariaSíNoSíNoSíNoSíNoAlgoritmo BusquedaBinariaAlgoritmo BusquedaBinariaDefinir datos, n, i, buscado, izquierda, derecha, medio, posicion, pasos Como EnteroDefinir datos, n, i, buscado,izquierda, derecha, medio,posicion, pasos Como EnteroEscribir "¿Cuántos números tiene la lista? (1 a 512)"Escribir "¿Cuántos númerostiene la lista? (1 a 512)"Leer nLeer nDimension datos[n]Dimension datos[n]Para i <- 1 Hasta n HacerPara i <- 1 Hasta ndatos[i] <- 2 * idatos[i] <- 2 * iMostrarDatos("Lista: ", datos, n)MostrarDatos("Lista: ",datos, n)buscado <- Aleatorio(1, 2 * n)buscado <- Aleatorio(1, 2 * n)Escribir "Buscando el ", buscadoEscribir "Buscando el ",buscadoizquierda <- 1izquierda <- 1derecha <- nderecha <- nposicion <- 0posicion <- 0pasos <- 0pasos <- 0Mientras izquierda <= derecha Y posicion = 0 Hacerizquierda <= derechaY posicion = 0medio <- Trunc((izquierda + derecha) / 2)medio <- Trunc((izquierda +derecha) / 2)pasos <- pasos + 1pasos <- pasos + 1Escribir " Paso ", pasos, ": miro la posición ", medio, " (", datos[medio], ")"Escribir " Paso ", pasos, ":miro la posición ", medio, "(", datos[medio], ")"Si datos[medio] = buscado Entoncesdatos[medio] =buscadoposicion <- medioposicion <- medioSi datos[medio] < buscado Entoncesdatos[medio] <buscadoizquierda <- medio + 1izquierda <- medio + 1derecha <- medio - 1derecha <- medio - 1Si posicion > 0 Entoncesposicion > 0Escribir "Encontrado: el ", buscado, " está en la posición ", posicion, "."Escribir "Encontrado: el ",buscado, " está en la posición", posicion, "."Escribir "El ", buscado, " no está en la lista."Escribir "El ", buscado, " noestá en la lista."Escribir "Comparaciones: ", pasos, " de ", n, " elementos."Escribir "Comparaciones: ",pasos, " de ", n, "elementos."FinAlgoritmoFinAlgoritmo
SubProceso MostrarDatos
SubProceso MostrarDatosSíNoSubProceso MostrarDatos(titulo, datos, n)SubProceso MostrarDatos(titulo,datos, n)Definir i Como EnteroDefinir i Como EnteroSi n <= 30 Entoncesn <= 30Escribir Sin Saltar tituloEscribir Sin Saltar tituloPara i <- 1 Hasta n HacerPara i <- 1 Hasta nEscribir Sin Saltar datos[i], " "Escribir Sin Saltar datos[i]," "Escribir ""Escribir ""Escribir titulo, n, " números (el primero es ", datos[1], " y el último ", datos[n], ")"Escribir titulo, n, " números(el primero es ", datos[1], "y el último ", datos[n], ")"FinSubProcesoFinSubProceso

Sample run

This is what the program shows when it runs. The answers typed by the user are highlighted.

¿Cuántos números tiene la lista? (1 a 512)User answer: 20Lista: 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 Buscando el 27  Paso 1: miro la posición 10 (20)  Paso 2: miro la posición 15 (30)  Paso 3: miro la posición 12 (24)  Paso 4: miro la posición 13 (26)  Paso 5: miro la posición 14 (28)El 27 no está en la lista.Comparaciones: 5 de 20 elementos.

Complexity

How much work and memory it needs as the amount of data (n) grows.

Complexity
CaseCost
BestO(1)
AverageO(log n)
WorstO(log n)
MemoryO(1)

Challenge

Also search for a number that surely isn't there, like 2 * n + 1, and count its steps.

Show hint

You can copy the search block or, better, turn it into a Funcion that returns the position.

Open in Codoritmo

Related examples

  • Bubble Sort

    Sorts random numbers by swapping neighbors, and stops as soon as they're in order.

    Intermediate

  • Insertion Sort

    Inserts each number among the sorted ones, like arranging cards in your hand.

    Intermediate

  • Shell Sort

    Insertion sort between far-apart elements, with a gap that shrinks every pass.

    Advanced