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?
d) 8

Passo 1

Beleza, vamos lá! Temos um vetor ordenado de forma crescente e queremos encontrar o número 80 usando o algoritmo de busca binária. Esse método é super eficiente para encontrar elementos em listas ordenadas. Para resolver, a gente vai precisar entender como a busca binária funciona e aplicar passo a passo até achar o número que estamos procurando.

Passo 2

Primeiro, vamos lembrar o que é a busca binária. Ela funciona dividindo o vetor em metades sucessivas até encontrar o valor desejado. A cada iteração, verificamos o elemento do meio:
  1. Se o elemento do meio for igual ao que procuramos, acabou!
  2. Se for menor, descartamos a metade esquerda e continuamos na direita.
  3. Se for maior, descartamos a metade direita e continuamos na esquerda.

Passo 3

Vamos aplicar isso ao nosso vetor:
Vetor: | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 |
Índices: 0  1   2   3   4   5   6   7   8
Iteração 1:
  • Início: esquerda = 0, direita = 8
  • Meio: (0 + 8) / 2 = 4 → índice 4 → valor 50
  • Comparação: 50 < 80 → descartamos a parte esquerda. Agora, esquerda = 5
Iteração 2:
  • Início: esquerda = 5, direita = 8
  • Meio: (5 + 8) / 2 = 6 → índice 6 → valor 70
  • Comparação: 70 < 80 → descartamos mais a esquerda. Agora, esquerda = 7
Iteração 3:
  • Início: esquerda = 7, direita = 8
  • Meio: (7 + 8) / 2 = 7 → índice 7 → valor 80
  • Comparação: 80 == 80 → Achei o número!

Resposta

O valor 80 será encontrado em 3 iterações usando a busca binária.

Exercícios relacionados