Entendendo Algoritimos (Bhargava): Busca Binária

A busca binária é uma técnica para encontrar um item em uma coleção ordenada, reduzindo o espaço de busca pela metade a cada passo.

Essa técnica só funciona quando há uma ordem conhecida: crescente, decrescente ou algum critério equivalente. Sem ordem, não há como descartar metade dos elementos com segurança.

Dada uma sequência ordenada:

\[ a_0, a_1, a_2, \ldots, a_{n-1} \]

com a propriedade:

\[ a_0 \leq a_1 \leq a_2 \leq \ldots \leq a_{n-1}, \]

queremos encontrar um valor \(x\).

Em cada passo, escolhemos um índice central:

\[ m = \left\lfloor \frac{S_i + S_f}{2} \right\rfloor \]

\(S_i\): início | \(S_f\): fim | \(\lfloor \ldots \rfloor\): arredondamento para baixo.

Depois, comparamos \(x\) com o valor armazenado no índice central, \(a_m\):

se \(x = a_m\), o item foi encontrado;
se \(x < a_m\), procuramos na metade esquerda;
se \(x > a_m\), procuramos na metade direita.

0.0.1 Busca Simples x Binária

Em uma busca simples, também chamada de busca linear ou sequencial, uma coleção com \(n\) elementos pode exigir até \(n\) comparações no pior caso, pois a busca percorre os elementos do primeiro até o último.

A busca binária reduz essa quantidade porque, a cada passo, o espaço de busca é dividido por 2:

\[ n,\ \frac{n}{2},\ \frac{n}{2^2},\ \frac{n}{2^3},\ \ldots,\ \frac{n}{2^k} \]

Para estimar quantas divisões são necessárias até restar aproximadamente um elemento, usamos:

\[ \frac{n}{2^k} \approx 1 \]

Logo:

\[ n \approx 2^k \]

Portanto:

\[ k \approx \log_2 n \]

Assim, a complexidade da busca binária é:

\[ O(\log n) \]

A base do logaritmo não altera a complexidade assintótica.

A conta \(\log_2 n\) representa a quantidade aproximada de reduções do intervalo. No pior caso de uma busca bem-sucedida, ainda é necessário comparar o valor com o último candidato. Por isso, a quantidade máxima de comparações é:

\[ \left\lfloor \log_2 n \right\rfloor + 1 \]

Exemplo:

Elementos	\(\log_2(n)\)	B. binária, pior caso	B. simples, pior caso	Complexidade
7	\(\approx 2{,}8\)	até 3 comparações	até 7 comparações	\(O(\log n)\)
8	\(3\)	até 4 comparações	até 8 comparações	\(O(\log n)\)
32	\(5\)	até 6 comparações	até 32 comparações	\(O(\log n)\)
1024	\(10\)	até 11 comparações	até 1024 comparações	\(O(\log n)\)
1048576	\(20\)	até 21 comparações	até 1048576 comparações	\(O(\log n)\)

Quando \(n\) não é uma potência de 2, o logaritmo não resulta em um número inteiro. A diferença de arredondamento e a comparação final não alteram a complexidade: ela continua sendo \(O(\log n)\).

0.0.2 Implementando a Busca Binária

Para começar a implementação, criei uma ideia de sistema:

O sistema escolhe um número dentro de um intervalo.
O usuário tenta adivinhar o número.
A cada tentativa, o sistema compara:
- se a tentativa for igual ao número secreto, o usuário ganhou;
- se a tentativa for menor que o número secreto, o número secreto é maior;
- se a tentativa for maior que o número secreto, o número secreto é menor.
O sistema conta quantas tentativas foram feitas.

Vou construir meu raciocínio em texto.

O sistema escolhe um número dentro de um intervalo.

Seja \(n_0\) o limite mínimo e \(n_1\) o limite máximo.

O limite mínimo é 1, e o limite máximo é escolhido aleatoriamente entre 50 e 500:

\[ n_0 = 1 \]

\[ n_1 = \texttt{MAX\_NUMBER} \]

O número secreto pertence ao intervalo \([n_0, n_1]\).

MAX_NUMBER=$(shuf -i 50-500 -n 1)
NUMBER=$(shuf -i "1-$MAX_NUMBER" -n 1)

O usuário tenta adivinhar.

read -r -p "Digite um palpite: " guess

A cada tentativa, o sistema compara:

se a tentativa for igual ao número secreto, o usuário ganhou;

se a tentativa for menor que o número secreto, o número secreto é maior;

se a tentativa for maior que o número secreto, o número secreto é menor.

if (( guess == NUMBER )); then
    echo "Acertou!"
elif (( guess > NUMBER )); then
    echo "Chute um número mais baixo."
else
    echo "Chute um número mais alto."
fi

O sistema conta quantas tentativas foram feitas.

attempts=0

while true; do
    ((attempts++))

    # Comparação do palpite.
done

O primeiro código ficou assim:

#!/usr/bin/env bash

max_number=$(shuf -i 50-500 -n 1)
number=$(shuf -i "1-$max_number" -n 1)
attempts=0 # Tentativas

while true; do
    ((attempts++))
    read -r -p "T.$attempts: Que nº eu escolhi? " guess

    if (( guess == number )); then
        echo "Acertou na $attemptsª tentativa."
        break
    elif (( guess > number )); then
        echo "Chute um nº mais baixo."
    else
        echo "Chute um nº mais alto."
    fi
done

Depois de escrever o primeiro código e entender melhor a busca binária, melhorei o controle das tentativas. Em vez de apenas informar se o palpite foi alto ou baixo, passei a guardar os limites já descobertos.

A lógica da função ficou assim:

A função aumenta a quantidade de tentativas.
Se o palpite for igual ao número secreto, o usuário acertou e o laço deve terminar.
Se o palpite for maior que o número secreto:
- se já existe um limite superior e o novo palpite é maior ou igual a esse limite, o programa avisa que essa informação já era conhecida;
- caso contrário, o palpite passa a ser o novo limite superior indicado.
Se o palpite for menor que o número secreto:
- se o novo palpite é menor ou igual ao limite inferior conhecido, o programa avisa que essa informação já era conhecida;
- caso contrário, o palpite passa a ser o novo limite inferior.
Se o usuário ainda não acertou, o laço continua.

#!/usr/bin/env bash

# loop      :: Variavel de controle para o loop do jogo
# high_next :: Dica do limite superior
# low_next  :: Dica do limite inferior
# message   :: Dica do palpite

check() {
    ((attempts++))

    if (( guess == NUMBER )); then
        echo "Acertou!" 
        loop=false

    elif (( guess > NUMBER )); then
        if ((high_next != 0 && guess >= high_next)); then
            message="Chutou Alto, mas você já sabia que o número era menor que $high_next."
        else
            high_next=$guess
            message="Chutou Alto."
        fi
        loop=true
        clear
    
    else
        if ((guess <= low_next)); then
            message="Chutou Baixo, mas você já sabia que o número era maior que $low_next."
        else
            low_next=$guess
            message="Chutou Baixo."
        fi
        loop=true
        clear
    fi
}

Depois disso, criei uma função para que a máquina também pudesse brincar.

A ideia foi criar um desafio para o usuário. Antes, o script apenas escolhia um número aleatoriamente. Agora, além disso, uma função tenta descobrir esse número sozinha usando a busca binária. Ao final, o programa informa ao usuário quantas tentativas a máquina realizou, criando nele a vontade de sempre acertar em menos tentativas.

#!/usr/bin/env bash

guess_system() {
    local start=1
    local end=$MAX_NUMBER
    local attempts_system=0
    local midpoint

    while (( start <= end )); do
        ((attempts_system++))
        midpoint=$(( (start + end) / 2 ))
        
        if (( midpoint == NUMBER )); then
            ideal_maximum_attempts=$attempts_system
            return 0
        elif (( midpoint < NUMBER )); then
            start=$((midpoint + 1))
        else
            end=$((midpoint - 1))
        fi
    done

    return 1
}

Por fim, alterei a estrutura do laço principal do jogo.

Antes de iniciar o laço, a função guess_system tenta descobrir o número escolhido usando a busca binária. A quantidade de tentativas realizadas pela máquina é armazenada para servir como referência ao usuário.

Durante o jogo, o programa mostra a quantidade de tentativas do usuário, a quantidade de tentativas da máquina e o intervalo no qual o número ainda pode estar. Assim, o usuário pode tentar descobrir o número antes da máquina.

O código completo ficou assim:

#!/usr/bin/env bash

# Define Constants
readonly MAX_NUMBER="$(shuf -i 50-500 -n 1)"
readonly NUMBER="$(shuf -i 1-"$MAX_NUMBER" -n 1)"

# Variables
attempts=0
low_next=0
high_next=0
guess=0
loop=true
message=""
ideal_maximum_attempts=0


check() {
    ((attempts++))

    if (( guess == NUMBER )); then
        echo "Acertou!" 
        loop=false

    elif (( guess > NUMBER )); then
        if ((high_next != 0 && guess >= high_next)); then
            message="Chutou Alto, mas você já sabia que o número era menor que $high_next."
        else
            high_next=$guess
            message="Chutou Alto."
        fi
        loop=true
        clear
    
    else
        if ((guess <= low_next)); then
            message="Chutou Baixo, mas você já sabia que o número era maior que $low_next."
        else
            low_next=$guess
            message="Chutou Baixo."
        fi
        loop=true
        clear
    fi
}

guess_system() {
    local start=1
    local end=$MAX_NUMBER
    local attempts_system=0
    local midpoint

    while (( start <= end )); do
        ((attempts_system++))
        midpoint=$(( (start + end) / 2 ))
        
        if (( midpoint == NUMBER )); then
            ideal_maximum_attempts=$attempts_system
            return 0
        elif (( midpoint < NUMBER )); then
            start=$((midpoint + 1))
        else
            end=$((midpoint - 1))
        fi
    done

    return 1
}

# Start Game
guess_system
clear
while $loop; do
    echo ""
    cat ascii-art.txt
    echo ""
    echo ""
    echo "Descubra o número que escolhi entre 1 - $MAX_NUMBER"
    echo ""
    echo "Tentativas: $attempts | Máximo Ideal: $ideal_maximum_attempts"
    echo "Baixo próximo: $low_next | Alto próximo: $high_next"
    echo "" 
    echo "$message"
    read -r -p "[$attempts] Digite seu palpite: " guess
    check
done

Versão HTML5 + CSS3 + JAVASCRIPT