Busca binária em array - Python

Olá, vou ensinar a fazer uma simples busca binária em python.

Primeiro você precisa saber o que é uma busca binária. Uma busca binária se consiste, basicamente, em dividir o array por 2 várias vezes até achar o número que você deseja encontrar.

Vamos direto ao código e você entenderá durante a explicação:

Em um array, temos o primeiro índice e o último, por exemplo:

lista = [2, 4, 6, 8, 10]

Lembrando que a lista que será feita a busca deverá estar ordenada

Nosso primeiro índice é o 0, nesse caso lista[0] = 2
O nosso último índice é o 4, nesse caso lista[4] = 10

Dito isso, seguimos:

low = 0
high = len(lista) - 1 

O método len nos retorna quantos elementos tem na lista, nesse caso, 5. Mas nós não queremos isso, queremos que high seja o último índice da nossa lista, por isso o -1 no final

Agora a gente precisa de um laço para percorrer nossa lista, vamos utilizar o laço while.

while(high >= low): 
        middle = (high + low) // 2
        if z == lst[middle]:
            return print('achou')
        else:
            if z < lst[middle]:
                high = middle - 1
            else:
                low = middle + 1 

Vamos lá, vou explicando linha a linha desse laço.

A condição que estamos passando no while é a seguinte: Enquanto nosso maior índice for maior que o nosso menor índice, execute o programa:

Se essa condição for verdadeira, a gente vai buscar a metade do array (lista) que declaramos logo no começo dessa explicação.

A metade do array vai receber a soma dos dois índices (maior e menor) dividida por 2, dizemos que high seja 4, teremos como metade
2.

middle = (high + low) // 2

Perfeito. Agora, vamos às verificações.
Se o nosso número buscado (nesse caso seria o parâmetro 'z') for igual a metade da nossa lista (lista[middle], que nesse caso é 2), então nós retornamos algo para nos mostrar que achamos o número buscado e acabamos o programa.

if z == lst[middle]:
   return print('achou')

Se o número buscado for diferente da metade da lista, vamos verificar se o número buscado é maior ou menor que a metade.

Se z (número buscado) < lista[middle] (metade), então a gente sabe que z está entre o primeiro número (low) e metade (middle), logo, sabemos que não precisamos mais dos números à direita da metade, não tendo porquê procurar por um número aonde ele não poderá estar.

Se essa verificação for verdadeira, então a partir de agora, o último número será a nova metade - 1 (Por que -1? Porque a gente tem a informação que nosso número é menor que a metade, então ele nunca poderá ser a metade, porém podendo ser um número a menos que ela)

if z < lst[middle]:
   high = middle - 1

Agora, se essa condição for falsa, só teremos mais uma condição a ser verificada, que seria z > lista[middle], já que já verificamos se z é == a metade ou z < metade.

Se z > metade, ignoraremos tudo que seja menor que a metade, já que z não poderá estar ali. Então, o que faremos? Nosso primeiro número será a nova metade + 1 (Novamente, por que +1? Porquê a gente sabe que z não é a metade, mas pode ser metade + 1)

else:
     low = middle + 1 

Feito isso, ele fará isso quantas vezes for necessário até que a condição do while retorne false. (Achar o número, ou não)