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 O e Omega ?

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, ini no início e fim no fim do vetor. Enquanto ini <= fim, calculamos o meio meio = lfloor(ini + fim)/2rfloor. Comparamos o valor no meio com o alvo. Se bater, achamos o índice; se o valor do meio for menor, descartamos a metade esquerda ( ini = meio + 1); senão descartamos a metade direita ( fim = meio - 1).
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
T(n) = Tl(n/2r) + C
onde C é constante.
Resolvendo essa recorrência (usando o teorema mestre ou expansão), chegamos que
T(n) = Clog2 n + D = O(log n)
No melhor caso (se o valor estiver logo no meio), paramos na primeira comparação, ou seja,
T(n) = Theta(1) = Omega(1)

Resposta

Algoritmo de busca binária conforme o pseudocódigo acima. A função de custo satisfaz T(n)=T(n/2)+C, resultando em complexidade de tempo O(log n) no pior caso e Omega(1) no melhor caso.

Exercícios relacionados