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
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:
- 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
- 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
- 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
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.
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.
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
e) 9