Busca sequencial em tabela ordenada:
A eficiência da operação de busca melhora se as chaves dos registros estiverem ordenadas:
*No pior caso (caso em que a chave não é encontrada), são necessárias N comparações quando as chaves estão desordenadas
*No caso médio, N/2 comparações se as chaves estiverem ordenadas, pois se para a busca assim que uma chave maior do que a procurada é encontrada.
Fonte: https://edisciplinas.usp.br/pluginfile.php/2175246/mod_resource/content/1/ICC2_12.Busca.pdf
@Rafael Costa, fiquei com a mesma dúvida que você, mas lendo com mais atenção o comentário que o @Guilherme Navarro escreveu, eu acho que entendi e vou tentar compartilhar o passo-a-passo que fiz usando um exemplo:
CASO 1) - Tenho o vetor A ordenado com os valores [12,25,33,37,48,57,86,92], onde N (tamanho) = 8 e desejo buscar pelo valor "51".
CASO 2)- Tenho vetor B não ordenado com os valores [56,12,67,98,34,08,33,10], onde N (tamanho) = 8 e desejo buscar pelo valor "51".
Agora copiando o a explicação do @Guilherme Navarro adicionando o exemplo:
*No pior caso (caso em que a chave não é encontrada), são necessárias N comparações quando as chaves estão desordenadas
No caso 2 - será necessário N comparações - ou seja - 8 comparações pois a ausência de ordenação obriga a percorrer todo o vetor em busca do valor 51.
*No caso médio, N/2 comparações se as chaves estiverem ordenadas, pois se para a busca assim que uma chave maior do que a procurada é encontrada.
No caso 1 - será necessário 6 comparações para descobrir que o valor 51 não consta no vetor e parar a leitura sequencial, uma vez que o valor 57 é maior que o valor procurado (51).
Logo, eu entendi que a ordenação ajuda no caso médio. Claro que mesmo ordenado, se o valor procurado é superior ao valor da última posição, você irá percorrer sequencialmente todo o vetor fazendo as N comparações - que também é o pior caso (procurar o valor 98 no vetor A).
Espero que tenha ajudado e caso o meu entedimento esteja equivocado podem me corrigir !
Vai haver uma melhora no desempenho porque o método de pesquisa sequencial é o mais simples, ele vai percorrendo o vetor sequencialmente, do primeiro ao último elemento do vetor.
Ex1.
[ 4 7 2 1 3 6 5] //repare que aqui o esforço será maior p organizar em sequencia, pq no final o método de pesquisa sequencnial irá deixar esse vetor assim: [4 7 2 1 3 6 5]
Ex2.
[1 2 3 4 5 6 7] //repare que se meus valores já estão organizados em sequencia o sacrifício de organizar os valores do vetor será totalmente eliminado, melhorando o desempenho.