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?
c) 4

Passo 1

Primeiro, vamos entender o que a questão está pedindo. Temos um vetor ordenado de forma ascendente:
Índice 0 1 2 3 4 5 6 7 8
Valor 10 20 30 40 50 60 70 80 90
Queremos descobrir quantas iterações são necessárias usando o algoritmo de busca binária para encontrar o valor 80. Para isso, precisamos entender como funciona a busca binária e aplicar passo a passo no nosso vetor.

Passo 2

O que é busca binária?
A busca binária é um método eficiente para encontrar um item em uma lista ordenada. Ela funciona dividindo a lista ao meio repetidamente até encontrar o item desejado ou até que não reste mais ninguém para verificar.
Como funciona?
  1. Identificar o meio: Verificamos o elemento do meio da lista.
  2. Comparar: Se o elemento do meio for o que estamos procurando, terminamos.
  3. Reduzir a busca: Se o elemento desejado for menor, repetimos a busca na metade esquerda; se for maior, na metade direita.
  4. Repetir: Continuamos esse processo até encontrar o elemento ou concluir que ele não está na lista.

Passo 3

Aplicando a busca binária no nosso vetor:
Vamos acompanhar cada iteração para ver quantas são necessárias para encontrar o valor 80.
  1. Iteração 1:
    • Vetor atual: 10, 20, 30, 40, 50, 60, 70, 80, 90
    • Índices: 0 a 8
    • Meio: Índice 4 (valor 50)
    • Comparação: 80 > 50
    • Ação: Procurar na metade direita (índices 5 a 8)
  2. Iteração 2:
    • Vetor atual: 60, 70, 80, 90
    • Índices: 5 a 8
    • Meio: Índice 6 (valor 70)
    • Comparação: 80 > 70
    • Ação: Procurar na metade direita (índices 7 a 8)
  3. Iteração 3:
    • Vetor atual: 80, 90
    • Índices: 7 a 8
    • Meio: Índice 7 (valor 80)
    • Comparação: 80 == 80
    • Ação: Valor encontrado!

Resposta

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

Exercícios relacionados