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?
b) 3

Passo 1

Então, temos um vetor ordenado de forma crescente com os valores 10, 20, 30, 40, 50, 60, 70, 80, 90 e queremos encontrar quantas vezes precisamos dividir esse vetor usando o algoritmo de busca binária para localizar o número 80. Vamos usar conceitos de busca binária para resolver isso!

Passo 2

Primeiro, vamos entender o que é a busca binária. É um método eficiente para encontrar um valor em um vetor ordenado dividindo o vetor ao meio a cada iteração. Em cada passo, comparamos o valor do meio com o valor que estamos procurando e descartamos metade do vetor com base nessa comparação.

Passo 3

Vamos aplicar isso no nosso vetor. O vetor tem índices de 0 a 8. Então, inicialmente:
  • Iteração 1:
    • Índice inicial (ESQ): 0
    • Índice final (DIR): 8
    • Índice do meio (MEIO):
    • Valor no meio: 50
    • Como 80 é maior que 50, descartamos a primeira metade e focamos na parte direita do vetor.

Passo 4

  • Iteração 2:
    • Novo ESQ: 5
    • Novo DIR: 8
    • Índice do meio:
    • Valor no meio: 70
    • Como 80 �� maior que 70, novamente descartamos a metade esquerda e focamos na parte direita.

Passo 5

  • Iteração 3:
    • Novo ESQ: 7
    • Novo DIR: 8
    • Índice do meio:
    • Valor no meio: 80
    • Achei! Encontramos o número 80 no terceiro passo.

Resposta

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

Exercícios relacionados