Dúvida sobre algoritmo binary search (pesquisa binária)

David, em linhas gerais, existem três grande fatores que eu levo em consideração na minha vida de engenheiro de software na hora de implementar uma algorítimo como esse.

1. Limite:

É importantíssimo entender em quais situações o tal algorítimo pode ser utilizado. Por exemplo, no caso da Binary Search ela só pode ser utilizada se o conjunto de dados estiver ordenado. Perceba que isso, de forma geral, já limita bastante os casos de uso.

Afinal, caso eu queria buscar algo em alguma outra estrutura de dados abstrata relativa a regra de negócio do meu produto, eu precisarei que ela suporte alguma noção de ordenadação para que a Binary Search possa ser utilizada, que nem sempre vai ser o caso.

2. Necessidade de Otimização:

"Otimização prematura é a raiz de todos os males" do Donald Knuth.

Acho faz bastante sentido buscar implementar um algorítmo melhor quando o problema exige. Porém, implementar algo melhor apenas pelo fato de ser mais performático tende a não ser boa prática.

Explico: Imagine que você está desenvolvendo um sistema web e, no front-end do projeto, ao fazer login, existe uma chamada para o back-end que retorna uma lista com 10 elementos e iremos utilizar alguma lógica par selecionar apenas um deles. Vamos dizer que esse elemento selecionado irá ser renderizado para nosso usuário assim que o algorítmo de busca finalizar.

Convenhamos, esse é um espaço amostral muito pequeno para se bucar uma otimização desse nível. Muito provavelmente a busca binária traria pouquíssima melhoria de performance porque o problema já é bem resolvido com busca linear (vamos convenciar para os exemplos que o find() de todas as linguaguens é uma busca linear, apesar de não ser o caso).

3. Código Limpo:

Aqui faço a uma referência ao famoso livro do Uncle Bob, no qual concordo bastante com a ideia tratada. Em resumo, gostaria de pontuar que o código limpo é aquele que consegue ser entendido facilmente. Portanto, isso é algo muito importante se levar em consideração na hora de implementar qualquer algorítmo não nátivo ou pouco usado (se comparado com outras soluções).

Pensa assim, eu acabo implementado uma linked list em um caso que um array seria o suficiente. Eu acabei de aumentar a complexidade de entendimento do meu código por conta disso. Claro, o que é "fácil" ou "difícil" varia muito de pessoa para pessoa, mas eu gosto de usar o absoluto: "quanto mais facilmente um código pode ser entendido por todos, melhor".

No meu primeiro trabalho, eu precisei resolver um problema em que montar uma árvore seria a melhor escolha. Eu tive alguns problema ao fazer isso e acabei pedindo ajuda aos meus colegas na época. Acredite, grande parte deles teve dificuldade em me ajudar dada a complexidade do algorítmo para o problema. Naquele momento, eu tive a certeza que mesmo aquele algorítmo sendo muito bom para o problema, ninguém iria conseguir da manutenção nele facilmente.

Em suma:

Portanto, eu penso que se existir um algóritmo que, definitivamente, resolve meu problema mais rápido do que outras soluções mais básicas, eu devo pensar:

• Esse problema realmente precisa dessa otimização?
• Esse algorítmo consegue ser lido, entendido e sofrer manutenção pelos meus colegas?
• (Em caso positivo das questões anteriores) Como posso fazer com que esse algorítmo seja o mais fácil entendido possível?

Sobre Binary Search

Acho que com o exposto, fica mais fácil de entender quando é necessário. Em linhas gerais, quando a Binary Search consegue ter um resultado MUITO melhor do que a busca linear (em grandes coleções de dados, que são/podem ser ordenadas). Qualquer sistema cujo o requsíto seja ser "fazer uma busca rápida entre elementos ordenados" ela será uma ótima candidata a ser implementada.

Fala, David! É uma dúvida justa kkkkk

Uma coisa importante pra gente se atentar é em relação a alocação de recursos. E que "instantâneo" não é bem uma medida, por ser uma coisa que varia muito a depender do referencial.

Por exemplo, se falamos de uma comporta de uma usina hidroelétrica e dizemos que ela se abre completamente em 5 segundos, isso pode ser considerado instantâneo. No entanto, se falamos de uma plataforma de Daytrade q leva 5 segundos pra submeter uma ordem isso pode ser uma eternidade kkkkkkk

E sobre alocação de recursos, esses algoritmos costumam ter por objetivo otimizar performance. Oq pode ser com velocidade, ou com economia de bits, por exemplo. Podem ser menos dados sendo armazenados na memória ram, ou menos dados sendo trafegados na rede, ou sla. No fim das contas, se vc extrapolar pr'um cenário com muitos dados e muitos usuários, a economia pode ser bastante expressiva, até.

Eu n tenho a resposta precisa que cê tá buscando, mas eu acho que com essa dúvida sua cê tá num caminho muito bom.

Fica aí o desafio pra vc cronometrar o tempo de execução da pesquisa normal do Python e da pesquisa utilizando o binary search (plmds, não é pra cronometrar com o celular, não, hein. É via código kkkkkk)

Dica simples pra vc cronometrar (não necessariamente a mais correta)

Importe o módulo nativo com time já importando o método a ser usado (q tbm se chama time), ficando

from time import time

Aí vc cria uma instância de inicio pra salvar o timestamp, e uma instância dps do fim do código. Aí vc calcula a duração do trecho fazendo a diferença do tempo final com o tempo inicial. E depois é só vc salvar isso numa variável e ajustar a formatação (a formatação eu n lembro de cabeça. Cê vai precisar dar uma pesquisada).

O resultado deve se parecer com isso

from time import time


def funcao_sua():
   inicio1 = time()
   [...seu código todo...]
   fim1 = time()
   duracao1 = fim1 - inicio1
   print(duracao1)
   
 
def binary_search():
   inicio2 = time()
   [...código todo...]
   fim2 = time()
   duracao2 = fim2 - inicio2
   print(duracao2)  


funcao_sua() 

binary_search()

Lembrando de ver como fazer a conversão do timestamp puro pra segundos. De cabeça eu não lembro, então vou ficar devendo kkkkkkk

Os colegas acima deram um parecer muito bem elaborado, dando apenas meus dois centavos:
Não se preocupe em sempre usar o MELHOR metodo/funcao/tec/recurso/lang, preocupe-se em resolver o problema da maneira mais simples, objetiva e fácil de dar manutenção.