Introdução a algoritmos (Cap. 1)

paráfrases, resumo e códigos com base no capítulo

Este capítulo fala sobre pesquisa binária, possui um código em Python aplicando a pesquisa binária e também aborda a notação Big O

Pesquisa binária

Imagina você procurando na lista de contatos alguém que comece com a letra N, provavelmente você vai começar a procurar a partir da letra N, até porque não tem necessidade de olhar as outras letras antes de N.

Num cenário onde o desenvolvedor precisa pesquisar entre uma grande quantidade de dados, onde se tem milhares de possibilidades, essa capacidade de buscar algo mais rapidamente seria muito interessante!

Com a pesquisa simples você teria que buscar informações de um em um. Nos seus contatos por exemplo, você teria que ir procurando de um em um até achar quem você quer. Numa quantidade pequena não seria tão demorado, né? Mas imagina 300 contatos... Já é um número maior e consideravelmente exaustivo de procurar de um por um.

É por isso que existe a pesquisa binária, ela visa resolver o problema da busca dividindo o total de items sempre pela metade até chegar em 1. Seguindo o exemplo da pesquisa numa lista de contatos, seria algo do tipo:

300 contatos => 150 => 75 => 37 => 18 => 9 => 4 => 2 => 1 contato

A grande diferença! Se fosse a pesquisa básica, teríamos de procurar de um em um, entre 300 contatos. Já usando a pesquisa binária, precisou apenas de 8 etapas! Sim, de 300 para 8.

IMPORTANTE: a lista de valores precisa estar em ordem para a pesquisa funcionar corretamente!

Abaixo o código de uma pesquisa binária feita em Python.

import math


def pesquisa_binaria(lista: list[int], valor_pesquisa: int) -> int | None:
    minimo = 0
    maximo = len(lista) - 1

    while minimo <= maximo:
        indice_meio = math.ceil((minimo + maximo) / 2)
        hipotese = lista[indice_meio]  # chute

        if hipotese == valor_pesquisa:
            return indice_meio

        if hipotese > valor_pesquisa:
            maximo = indice_meio - 1
        else:
            minimo = indice_meio + 1

    return None


numeros = [1, 2, 4, 9, 10, 16, 18]
numero_pesquisa = 4
resultado_pesquisa = pesquisa_binaria(numeros, numero_pesquisa)

print(f"O índice do número {numero_pesquisa} é: {resultado_pesquisa}")
# O índice do número 4 é: 2

Tempo de execução (Big O)

Na tabela cima, vemos uma diferença gritante entre a pesquisa simples e a pesquisa binária. A notação Big O é uma notação especial que diz o quão rápido é um algoritmo.

Exemplos comuns de tempo de execução Big O

  • O(log n), também conhecido como tempo logarítmico. Exemplo: pesquisa binária

  • O(n), conhecido como tempo linear. Exemplo: pesquisa simples.

  • O(n * log n): um algoritmo rápido de ordenação, como a ordenação quicksort (explicada no Capítulo 4).

  • O(n2): um algoritmo lento de ordenação, como a ordenação por seleção (explicada no Capítulo 2).

  • O(n!): um algoritmo bastante lento, como o do caixeiro-viajante (explicado a seguir!)

a lista acima foi retirada diretamente do livro

Conclusões do capítulo

  • A pesquisa binária é muito mais rápida do que a pesquisa simples.

  • O(log n) é mais rápido do que O(n), e O(log n) fica ainda mais rápido conforme os elementos da lista aumentam.

  • A rapidez de um algoritmo não é medida em segundos.

  • O tempo de execução de um algoritmo é medido por meio de seu crescimento.

  • O tempo de execução dos algoritmos é expresso na notação Big O.

a lista acima foi retirada diretamente do livro

NextOrdenação por seleção (Cap. 2)

Last updated