Seja o seguinte vetor, ordenado de forma ascendente:
10 20 30 40 50 60 70 80 90
0 1 2 3 4 5 6 7 8
Caso se utilize um algoritmo de busca binária, quantas iterações serão necessárias para que o valor 80 seja encontrado?
e) 9

Passo 1

Vamos resolver esse exercício usando busca binária, que é uma técnica eficiente para encontrar um elemento em um vetor que já está ordenado. O vetor que temos está em ordem crescente e queremos descobrir quantas tentativas a busca binária leva para encontrar o valor 80. Para isso, precisamos entender como a busca binária funciona e aplicá-la passo a passo.

Passo 2

Primeiro, vamos identificar os índices e os valores no vetor:
Índice 0 1 2 3 4 5 6 7 8
Valor 10 20 30 40 50 60 70 80 90
A busca binária começa verificando o elemento do meio do vetor. Com 9 elementos, o meio está no índice:
meio = lfloor 0 + 82 rfloor = 4
Então, olhamos para o valor no índice 4, que é 50.

Passo 3

Comparando 80 com 50, vemos que 80 é maior. Isso significa que o valor que estamos procurando está na metade superior do vetor. Então, descartamos a parte inferior e focamos nos índices de 5 a 8.

Passo 4

Agora, nosso novo intervalo é de índices 5 a 8. Vamos encontrar o novo ponto médio:
meio = lfloor 5 + 82 rfloor = 6
O valor no índice 6 é 70.

Passo 5

Comparando 80 com 70, vemos novamente que 80 é maior. Portanto, descartamos a metade inferior desse intervalo e nos concentramos nos índices de 7 a 8.

Passo 6

Com o intervalo reduzido a índices 7 a 8, encontramos o novo ponto médio:
meio = lfloor 7 + 82 rfloor = 7
O valor no índice 7 é 80, que é o valor que estamos procurando!

Resposta

Foram necessárias 3 iterações para encontrar o valor 80 usando busca binária.

Exercícios relacionados