Escreva um algoritmo que procure por um dado número em vetor ordenado. Quais são sua função de custo e ordens de complexidade
e
?
Passo 1
O problema pede para a gente achar um número em um vetor já ordenado. O conteúdo aqui é busca binária e vamos precisar da ideia de dividir o vetor ao meio para eliminar metade das possibilidades a cada comparação.
Passo 2
A busca binária funciona assim: começamos com dois índices,
no início e
no fim do vetor. Enquanto
, calculamos o meio
. Comparamos o valor no meio com o alvo. Se bater, achamos o índice; se o valor do meio for menor, descartamos a metade esquerda (
); senão descartamos a metade direita (
).
Veja o pseudocódigo:
Veja o pseudocódigo:
function buscaBinaria(vetor, x):
ini = 1
fim = length(vetor)
while ini <= fim:
meio = floor((ini + fim)/2)
if vetor[meio] == x:
return meio
if vetor[meio] < x:
ini = meio + 1
else:
fim = meio - 1
return -1
Passo 3
Para analisar a função de custo, note que cada iteração faz um número constante de operações (comparações e cálculo de índice) e reduz o problema pela metade. Assim temos a recorrência
onde
Resolvendo essa recorrência (usando o teorema mestre ou expansão), chegamos que
No melhor caso (se o valor estiver logo no meio), paramos na primeira comparação, ou seja,
Resposta
Algoritmo de busca binária conforme o pseudocódigo acima. A função de custo satisfaz
, resultando em complexidade de tempo
no pior caso e
no melhor caso.