Skip to content
ExamplesEspañolWorkspace →

Linear vs. Binary Search

Counts the comparisons each search needs on the same sorted list.

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

Run, change and debug this example in your browser.

What you'll learn

Two functions search for the same value and return how many comparisons they made. Linear search checks one by one: O(1) if the value comes first, O(n) if it's last or missing. Binary search never needs more than log n comparisons. Try n = 10 and n = 500 to see them drift apart.

Code

search-comparison.psc · 79 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], ")"    FinSiFinSubProceso// Revisa los elementos uno por uno; devuelve cuántas comparaciones hizoFuncion comparaciones <- BuscarLineal(datos, n, buscado)    Definir comparaciones, i Como Entero    Definir encontrado Como Logico    comparaciones <- 0    encontrado <- Falso    i <- 1    Mientras i <= n Y (NO encontrado) Hacer        comparaciones <- comparaciones + 1        Si datos[i] = buscado Entonces            encontrado <- Verdadero        FinSi        i <- i + 1    FinMientrasFinFuncion// Parte el rango a la mitad en cada paso; devuelve cuántas comparaciones hizoFuncion comparaciones <- BuscarBinaria(datos, n, buscado)    Definir comparaciones, izquierda, derecha, medio Como Entero    Definir encontrado Como Logico    comparaciones <- 0    encontrado <- Falso    izquierda <- 1    derecha <- n    Mientras izquierda <= derecha Y (NO encontrado) Hacer        medio <- Trunc((izquierda + derecha) / 2)        comparaciones <- comparaciones + 1        Si datos[medio] = buscado Entonces            encontrado <- Verdadero        SiNo            Si datos[medio] < buscado Entonces                izquierda <- medio + 1            SiNo                derecha <- medio - 1            FinSi        FinSi    FinMientrasFinFuncionAlgoritmo CompararBusquedas    Definir datos, objetivos, n, i, mitades, resto Como Entero    Escribir "¿Cuántos números tiene la lista? (1 a 512)"    Leer n    Dimension datos[n], objetivos[4]    Para i <- 1 Hasta n Hacer        datos[i] <- 2 * i    FinPara    MostrarDatos("Lista: ", datos, n)    // Cuatro casos: el primero, uno al azar, el último y uno que no está (impar)    objetivos[1] <- datos[1]    objetivos[2] <- datos[Aleatorio(1, n)]    objetivos[3] <- datos[n]    objetivos[4] <- 2 * Aleatorio(1, n) - 1    Para i <- 1 Hasta 4 Hacer        Escribir "Buscar el ", objetivos[i], " -> comparaciones: lineal ", BuscarLineal(datos, n, objetivos[i]), ", binaria ", BuscarBinaria(datos, n, objetivos[i])    FinPara    // Cuántas veces se puede partir n a la mitad: el peor caso de la binaria    mitades <- 0    resto <- n    Mientras resto > 0 Hacer        mitades <- mitades + 1        resto <- Trunc(resto / 2)    FinMientras    Escribir "Peor caso con ", n, " elementos: lineal ", n, ", binaria ", mitades, "."FinAlgoritmo

Flowchart

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

Algoritmo CompararBusquedas
Algoritmo CompararBusquedasSíNoAlgoritmo CompararBusquedasAlgoritmo CompararBusquedasDefinir datos, objetivos, n, i, mitades, resto Como EnteroDefinir datos, objetivos, n,i, mitades, resto 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], objetivos[4]Dimension datos[n],objetivos[4]Para i <- 1 Hasta n HacerPara i <- 1 Hasta ndatos[i] <- 2 * idatos[i] <- 2 * iMostrarDatos("Lista: ", datos, n)MostrarDatos("Lista: ",datos, n)objetivos[1] <- datos[1]objetivos[1] <- datos[1]objetivos[2] <- datos[Aleatorio(1, n)]objetivos[2] <-datos[Aleatorio(1, n)]objetivos[3] <- datos[n]objetivos[3] <- datos[n]objetivos[4] <- 2 * Aleatorio(1, n) - 1objetivos[4] <- 2 *Aleatorio(1, n) - 1Para i <- 1 Hasta 4 HacerPara i <- 1 Hasta 4Escribir "Buscar el ", objetivos[i], " -> comparaciones: lineal ", BuscarLineal(datos, n, objetivos[i]), ", binaria ", BuscarBinaria(datos, n, objetivos[i])Escribir "Buscar el ",objetivos[i], " ->comparaciones: lineal ",…mitades <- 0mitades <- 0resto <- nresto <- nMientras resto > 0 Hacerresto > 0mitades <- mitades + 1mitades <- mitades + 1resto <- Trunc(resto / 2)resto <- Trunc(resto / 2)Escribir "Peor caso con ", n, " elementos: lineal ", n, ", binaria ", mitades, "."Escribir "Peor caso con ", n," elementos: lineal ", n, ",binaria ", mitades, "."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
Funcion BuscarLineal
Funcion BuscarLinealSíNoSíNoFuncion comparaciones <- BuscarLineal(datos, n, buscado)Funcion comparaciones <-BuscarLineal(datos, n, buscado)Definir comparaciones, i Como EnteroDefinir comparaciones, i ComoEnteroDefinir encontrado Como LogicoDefinir encontrado Como Logicocomparaciones <- 0comparaciones <- 0encontrado <- Falsoencontrado <- Falsoi <- 1i <- 1Mientras i <= n Y (NO encontrado) Haceri <= n Y (NOencontrado)comparaciones <- comparaciones + 1comparaciones <- comparaciones+ 1Si datos[i] = buscado Entoncesdatos[i] = buscadoencontrado <- Verdaderoencontrado <- Verdaderoi <- i + 1i <- i + 1FinFuncion (devuelve comparaciones)FinFuncion (devuelvecomparaciones)
Funcion BuscarBinaria
Funcion BuscarBinariaSíNoSíNoSíNoFuncion comparaciones <- BuscarBinaria(datos, n, buscado)Funcion comparaciones <-BuscarBinaria(datos, n, buscado)Definir comparaciones, izquierda, derecha, medio Como EnteroDefinir comparaciones,izquierda, derecha, medio ComoEnteroDefinir encontrado Como LogicoDefinir encontrado Como Logicocomparaciones <- 0comparaciones <- 0encontrado <- Falsoencontrado <- Falsoizquierda <- 1izquierda <- 1derecha <- nderecha <- nMientras izquierda <= derecha Y (NO encontrado) Hacerizquierda <= derechaY (NO encontrado)medio <- Trunc((izquierda + derecha) / 2)medio <- Trunc((izquierda +derecha) / 2)comparaciones <- comparaciones + 1comparaciones <- comparaciones+ 1Si datos[medio] = buscado Entoncesdatos[medio] =buscadoencontrado <- Verdaderoencontrado <- VerdaderoSi datos[medio] < buscado Entoncesdatos[medio] <buscadoizquierda <- medio + 1izquierda <- medio + 1derecha <- medio - 1derecha <- medio - 1FinFuncion (devuelve comparaciones)FinFuncion (devuelvecomparaciones)

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: 100Lista: 100 números (el primero es 2 y el último 200)Buscar el 2 -> comparaciones: lineal 1, binaria 6Buscar el 120 -> comparaciones: lineal 60, binaria 6Buscar el 200 -> comparaciones: lineal 100, binaria 7Buscar el 111 -> comparaciones: lineal 100, binaria 7Peor caso con 100 elementos: lineal 100, binaria 7.

Complexity

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

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

Challenge

Compute the average number of comparisons of each search by looking up every value in the list.

Show hint

Loop i from 1 to n, search for datos[i] with both functions and add up the results; divide by n at the end.

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