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

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

Exercícios relacionados

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.
Com relação às estruturas de dados em listas, analise as afirmativas a seguir.
I. Em uma lista não ordenada, os elementos devem estar organizados em ordem decrescente das respectivas chaves.
II. Uma lista encadeada é uma estrutura de dados, na qual os objetos estão organizados em ordem linear.
III. Em uma lista duplamente encadeada, cada elemento deve apontar para o elemento anterior e para o próximo.
Está correto o que se afirma em:
d) II e III, apenas.
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
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.