Sim, é pre-requisito da busca binária que a lista em questão esteja ordenada.

Se não tiver como garantir que os elementos inseridos na lista sejam inseridos ordenados, provavelmente não vale apena ordenar e aplicar busca binária.

Mas vale a pena fazer uma análise.
Encontrar um elemento em uma lista é O(n), enquanto a busca binária é (logn), um algoritmo de ordenação é de O(nlogn) ~ O(n²), dependendo de qual você esteja usando. Se tiver propriedades muito específicas você conseguiria ordenar até com O(n) com Radix Sort, mas não acho que seja o caso. Por fim, usar qualquer desses juntamente a busca binária daria O(logn + nlogn) que é O(nlogn), ou seja, ficaria melhor usar busca simples na lista.

Claro, tô imaginando o cenário mais simples possível pq você não falou muito, se por exemplo forem realizadas várias buscas consecutivas no mesmo array, ordenar e realizar apenas buscas binárias pode melhorar a performace.

Por fim, termino incentivando você a pesquisar um pouco mais antes de perguntar. Pois qualquer pesquisa rápida responderia que busca binária exige que a entrada esteja ordenada (Se não não dá para saber para qual lado deve ir).

Outra coisa, se a pesquisa está lenta, avalie se lista é a melhor estrutura de dados para o problema em questão.