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
Passo 1
Então, temos um vetor ordenado de forma crescente com os valores
e queremos encontrar quantas vezes precisamos dividir esse vetor usando o algoritmo de busca binária para localizar o número 80. Vamos usar conceitos de busca binária para resolver isso!
Passo 2
Primeiro, vamos entender o que é a busca binária. É um método eficiente para encontrar um valor em um vetor ordenado dividindo o vetor ao meio a cada iteração. Em cada passo, comparamos o valor do meio com o valor que estamos procurando e descartamos metade do vetor com base nessa comparação.
Passo 3
Vamos aplicar isso no nosso vetor. O vetor tem índices de 0 a 8. Então, inicialmente:
- Iteração 1:
- Índice inicial (ESQ): 0
- Índice final (DIR): 8
- Índice do meio (MEIO):
- Valor no meio: 50
- Como 80 é maior que 50, descartamos a primeira metade e focamos na parte direita do vetor.
Passo 4
- Iteração 2:
- Novo ESQ: 5
- Novo DIR: 8
- Índice do meio:
- Valor no meio: 70
- Como 80 �� maior que 70, novamente descartamos a metade esquerda e focamos na parte direita.
Passo 5
- Iteração 3:
- Novo ESQ: 7
- Novo DIR: 8
- Índice do meio:
- Valor no meio: 80
- Achei! Encontramos o número 80 no terceiro passo.
Resposta
Serão necessárias 3 iterações para encontrar o valor 80 usando o algoritmo de busca binária.
Exercícios relacionados
- 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 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?
a) A Inserção de um novo nó e remoção de um nó.
a) A Inserção de um novo nó e remoção de um nó.
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
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.