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?
a) 2

Passo 1

Beleza, vamos resolver essa questão juntos! O enunciado nos apresenta uma tabela com valores ordenados e nos pergunta quantas vezes precisamos dividir o conjunto (iterações) usando o algoritmo de busca binária para encontrar o valor 80. A matéria envolvida aqui é Algoritmos de Busca, mais especificamente a Busca Binária. Para resolver isso, vamos precisar entender como a busca binária funciona e aplicá-la passo a passo na tabela fornecida.

Passo 2

Primeiro, vamos entender o que é a busca binária. É um método eficiente para encontrar um elemento em uma lista ordenada. A ideia é dividir a lista ao meio repetidamente, comparando o elemento do meio com o valor que estamos procurando, e assim reduzir o espaço de busca pela metade a cada iteração.
Nossa tabela é:
Índice 0 1 2 3 4 5 6 7 8
Valor 10 20 30 40 50 60 70 80 90
Queremos encontrar o valor 80.

Passo 3

Vamos iniciar a busca binária:
  1. Primeira iteração:
    • Limites da busca: início = 0, fim = 8
    • Elemento do meio: índice = (0 + 8) / 2 = 4 (considerando divisão inteira)
    • Valor encontrado: 50
    • Comparação: 80 > 50, então o valor procurado está na metade direita da lista.
    • Novo intervalo de busca: início = 5, fim = 8
    • Iterações realizadas: 1

Passo 4

  1. Segunda iteração:
    • Limites da busca: início = 5, fim = 8
    • Elemento do meio: índice = (5 + 8) / 2 = 6
    • Valor encontrado: 70
    • Comparação: 80 > 70, então o valor procurado está na metade direita da nova lista.
    • Novo intervalo de busca: início = 7, fim = 8
    • Iterações realizadas: 2

Passo 5

  1. Terceira iteração:
    • Limites da busca: início = 7, fim = 8
    • Elemento do meio: índice = (7 + 8) / 2 = 7
    • Valor encontrado: 80
    • Comparação: 80 == 80, encontramos o valor!
    • Iterações realizadas: 3

Resposta

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

Exercícios relacionados

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
Em uma Árvore Binária de Busca (BST) balanceada, qual das seguintes operações geralmente exibe uma complexidade de tempo média de , considerando a estrutura balanceada da árvore?
b) Remoção de um nó e busca por um elemento.
Uma lista ligada é uma estrutura que corresponde a uma sequência lógica de entradas ou nós. Cada nó armazena a localização do próximo elemento na sequência, ou seja, de seu nó sucessor. Nessa estrutura,
a) Para estabelecer a ligação entre um nó já pertencente a uma lista e um novo nó, basta fazer com que o novo nó referencie no, campo next, o nó que anteriormente era referenciado pelo nó original, desde que esse campo não tenha o valor nulo.
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?
e) 9