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.