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
Passo 1
Vamos resolver esse exercício usando busca binária, que é uma técnica eficiente para encontrar um elemento em um vetor que já está ordenado. O vetor que temos está em ordem crescente e queremos descobrir quantas tentativas a busca binária leva para encontrar o valor 80. Para isso, precisamos entender como a busca binária funciona e aplicá-la passo a passo.
Passo 2
Primeiro, vamos identificar os índices e os valores no vetor:
Índice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
Valor | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 |
A busca binária começa verificando o elemento do meio do vetor. Com 9 elementos, o meio está no índice:
Então, olhamos para o valor no índice 4, que é 50.
Passo 3
Comparando 80 com 50, vemos que 80 é maior. Isso significa que o valor que estamos procurando está na metade superior do vetor. Então, descartamos a parte inferior e focamos nos índices de 5 a 8.
Passo 4
Agora, nosso novo intervalo é de índices 5 a 8. Vamos encontrar o novo ponto médio:
O valor no índice 6 é 70.
Passo 5
Comparando 80 com 70, vemos novamente que 80 é maior. Portanto, descartamos a metade inferior desse intervalo e nos concentramos nos índices de 7 a 8.
Passo 6
Com o intervalo reduzido a índices 7 a 8, encontramos o novo ponto médio:
O valor no índice 7 é 80, que é o valor que estamos procurando!
Resposta
Foram necessárias 3 iterações para encontrar o valor 80 usando busca binária.
Exercícios relacionados
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.
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
Um dos exemplos de estrutura de dados é a lista encadeada simples. Com relação a esse tipo de lista, é correto afirmar:
d) Na inserção de um novo elemento, é necessário realizar a atualização dos ponteiros dos elementos envolvidos, não sendo necessário realizar o deslocamento físico dos elementos.
d) Na inserção de um novo elemento, é necessário realizar a atualização dos ponteiros dos elementos envolvidos, não sendo necessário realizar o deslocamento físico dos elementos.
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,
e) o armazenamento de uma lista não requer uma área contígua de memória. Como listas são estruturas dinâmicas, normalmente são definidos procedimentos que permitem criar e remover nós na memória.
e) o armazenamento de uma lista não requer uma área contígua de memória. Como listas são estruturas dinâmicas, normalmente são definidos procedimentos que permitem criar e remover nós na memória.