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
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:
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:
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:
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.