Introdução a algoritmos: Pesquisa binária

Introdução

Algoritmo é um conjunto de instruções que realizam uma tarefa.

Pesquisa Binária

Vamos supor que você entre no Facebook. Ao fazer isso, o Facebook precisa verificar se você tem uma conta no site. Logo, ele procura seu nome de usuário em um banco de dados. Digamos que seu usuário seja "TonyStark". O Facebook poderia começar pela letra "A" para procurar seu nome, mas faz mais sentido começar pelo meio.

Isso é um problema de busca. E todos esses casos usam um algoritmo para resolvê-lo: Pesquisa Binária.

A pesquisa binária é um algoritmo cuja entrada é uma lista ordenada de elementos. Se o elemento que você está buscando está na lista, a pesquisa binária retorna sua localização. Caso contrário, a pesquisa binária retorna None.

Nota: A pesquisa binária só funciona quando a lista está ordenada. Por exemplo, os nomes em uma agenda telefônica estão em ordem alfabética.

Vamos escrever a pesquisa binária em Python. O exemplo de código que utilizaremos aqui usa arrays. A função pesquisa_binaria recebe um array ordenado e um item. Se o item estiver no array, a função retorna sua posição. Dessa maneira, você sabe a partir de qual ponto do array deve continuar procurando. No início, o código do array segue assim:

baixo = 0
alto = len(lista) - 1

meio = (baixo + alto) // 2
chute = lista[meio]

Nota: meio será arredondado para baixo automaticamente pelo Python se (baixo + alto) não for um número par.

Se o chute for baixo, você atualizará a variável baixo proporcionalmente:

if chute < item:
    baixo = meio + 1

E se o chute for muito alto, você atualizará a variável alto. Aqui está o código completo:

def pesquisa_binaria(lista, item):
     baixo = 0
     alto = len(lista) - 1

     while baixo <= alto:
          meio = (baixo + alto) // 2
          chute = lista[meio]
          if chute == item:
              return meio
          if chute > item:
              alto = meio - 1
          else:
              baixo = meio + 1
     return None

minha_lista = [1, 3, 5, 7, 9]

print(pesquisa_binaria(minha_lista, 3)) # => 1
print(pesquisa_binaria(minha_lista, -1)) # => None

Explicação

• baixo e alto acompanham a parte da lista que você está procurando;
• Enquanto ainda não chegou a um único elemento, verifique o elemento central;
• Encontre o item;
• O chute foi muito alto;
• O chute foi muito baixo;
• O item não existe;
• Vamos testá-lo;
• Lembre-se: as listas começam no índice 0. O próximo endereço tem índice 1;
• None significa nulo em Python. Ele indica que o item não foi encontrado.

Livro de referência: Para um entendimento mais profundo sobre algoritmos, recomendo o livro "Entendendo Algoritmos: Um Guia Ilustrado para Programadores e Outros Curiosos" de Aditya Y. Bhargava. Esse livro fornece explicações claras e ilustradas de diversos algoritmos, incluindo a pesquisa binária.