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
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?
- Identificar o meio: Verificamos o elemento do meio da lista.
- Comparar: Se o elemento do meio for o que estamos procurando, terminamos.
- Reduzir a busca: Se o elemento desejado for menor, repetimos a busca na metade esquerda; se for maior, na metade direita.
- 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.
-
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)
-
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)
-
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.