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
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:
- Se o elemento do meio for igual ao que procuramos, acabou!
- Se for menor, descartamos a metade esquerda e continuamos na direita.
- 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
Í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.