Ótima análise! De fato, se formos avaliar a implementação real do código no post, a conversão para set ali não faz sentido e acaba piorando a performance. A intenção era mostrar como a escolha da estrutura de dados pode impactar a eficiência, mas concordo que o exemplo não foi feliz e acabou gerando um efeito contrário.

Seu ponto sobre busca binária faz total sentido, e considerando a estrutura interna de list e set, há diversos fatores além da complexidade assintótica que influenciam no desempenho real, como consumo de memória, cache locality e até o comportamento do GC.

A lição que fica disso tudo é que otimização não é apenas sobre big-O, mas também sobre o comportamento real das estruturas e do hardware. Obrigado pelo comentário, sempre bom discutir esses detalhes!