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
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?
- Identificar o meio: Verificamos o elemento do meio da lista.
- Comparar: Se o elemento do meio for o que estamos procurando, terminamos.
- Reduzir a busca: Se o elemento desejado for menor, repetimos a busca na metade esquerda; se for maior, na metade direita.
- 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.
-
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)
-
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)
-
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
b) 3
- Escolha um elemento que será chamado o pivot da lista.
- 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. - 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.
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.
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.