Até onde eu sei as duas formas de acessar uma chave no dicionário são basicamente equivalentes (claro uma retorna um booleano da existência e o outro retorna o valor, mas ambas conseguem tempo O(1), na maioria dos casos (tem casos extremos que pode ser O(n), mas que não chegam nem perto de ocorrer)).
Dicionários são tabelas de espalhamento, elas possuem performance quase ao do array para acesso aleatório, só perde um pouco porque precisa calcular o código hash antes de acessar o elemento. Existem casos de colisão de chaves onde a busca precisa ser feita de outra forma, podendo até mesmo chegar em complexidade O(n).
Um dicionário é quase o oposto de uma estrutura que permite busca binária. Um dicionário não pode estar nem ordenado (com regra específica), muito menos classificado (com critério determinado).
No exemplo tenho dúvidas se um array não seria a melhor escolha.
Tanto o array,quanto o dicionário terá complexidade O(n) para procurar por valores.
Já demonstrei que o dicionário é diferente do array.
Pode ser útil: Objetos são semelhantes a arrays?.
Coloquei no GitHub para referência futura.