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?
c) 4

Passo 1

Primeiro, vamos entender o que a questão está pedindo. Temos um vetor ordenado de forma ascendente:
Índice 0 1 2 3 4 5 6 7 8
Valor 10 20 30 40 50 60 70 80 90
Queremos descobrir quantas iterações são necessárias usando o algoritmo de busca binária para encontrar o valor 80. Para isso, precisamos entender como funciona a busca binária e aplicar passo a passo no nosso vetor.

Passo 2

O que é busca binária?
A busca binária é um método eficiente para encontrar um item em uma lista ordenada. Ela funciona dividindo a lista ao meio repetidamente até encontrar o item desejado ou até que não reste mais ninguém para verificar.
Como funciona?
  1. Identificar o meio: Verificamos o elemento do meio da lista.
  2. Comparar: Se o elemento do meio for o que estamos procurando, terminamos.
  3. Reduzir a busca: Se o elemento desejado for menor, repetimos a busca na metade esquerda; se for maior, na metade direita.
  4. Repetir: Continuamos esse processo até encontrar o elemento ou concluir que ele não está na lista.

Passo 3

Aplicando a busca binária no nosso vetor:
Vamos acompanhar cada iteração para ver quantas são necessárias para encontrar o valor 80.
  1. Iteração 1:
    • Vetor atual: 10, 20, 30, 40, 50, 60, 70, 80, 90
    • Índices: 0 a 8
    • Meio: Índice 4 (valor 50)
    • Comparação: 80 > 50
    • Ação: Procurar na metade direita (índices 5 a 8)
  2. Iteração 2:
    • Vetor atual: 60, 70, 80, 90
    • Índices: 5 a 8
    • Meio: Índice 6 (valor 70)
    • Comparação: 80 > 70
    • Ação: Procurar na metade direita (índices 7 a 8)
  3. Iteração 3:
    • Vetor atual: 80, 90
    • Índices: 7 a 8
    • Meio: Índice 7 (valor 80)
    • Comparação: 80 == 80
    • Ação: Valor encontrado!

Resposta

Foram necessárias 3 iterações para encontrar o valor 80 usando 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?
b) 3
  1. Escolha um elemento que será chamado o pivot da lista.
  2. Reordene a lista de tal forma que os elementos menores que o pivot venham antes dele e os elementos maiores ou iguais ao pivot venham depois dele. Essa operação é chamada de partição, e cria duas sublistas:
    a. a de menores que o pivot
    b. a de maiores ou iguais ao pivot.
  3. Aplique recursivamente os passos 1 e 2 às sublistas de menores e maiores que o pivot. O algoritmo acima corresponde ao:
    a) Quicksort, e faz, em média, comparações para ordenar itens.
Em relação ao tipo de estrutura de dados conhecido como lista ligada ou lista encadeada, é correto afirmar que:
e) A sucessão dos elementos é determinada por um ponteiro que indica a posição do próximo 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:
b) I e II, apenas.