Geral
Algoritmos e Programação de Computadores II
Semana 3
0

Questão

O algoritmo de busca binária considera um vetor ordenado de n elementos para realizar a varredura dos elementos, por isso é possível implementar um algoritmo mais eficiente do que aquele que utiliza a busca sequencial. Adotando o paradigma dividir para conquistar, o problema global é dividido em subproblemas, o que faz com que o espaço de busca se reduza à metade a cada iteração do algoritmo.

Com relação ao algoritmo de busca binária apresentado, avalie as afirmações a seguir. 

I.  Se n for um valor pequeno, o custo adicional para ordenar a lista pode não compensar.

II. As comparações requeridas começam com uma lista de tamanho n/2, depois n/4, depois n/6, depois n/8 e assim sucessivamente enquanto o elemento procurado não tiver sido encontrado, e a lista não for vazia.

III. O número máximo de comparações requeridas é dado por nlog ( n ).

IV. A análise da busca binária elimina metade dos itens que restam a cada comparação.

Está correto que se afirma em:
A)

II e III, apenas.

B)

I e IV, apenas.

C)

III e IV, apenas. 

D)

I e III, apenas. 

E)

II e IV, apenas. 

function vote(questaoId, value) { window.location.href = "/accounts/login/?next=/questao/811/"; return; fetch(`/vote/questao/${questaoId}/`, { method: 'POST', headers: { 'Content-Type': 'application/json', 'X-CSRFToken': 'axeMZTlbis3Opyq5Z1wNImNZ7zsFdxAgpyEZCYPsP195bC5mUoIHBBLdHcqYxhXI' }, body: JSON.stringify({ value: value }) }) .then(response => response.json()) .then(data => { if (data.success) { document.getElementById(`score-${questaoId}`).textContent = data.score; const upBtn = document.querySelector(`button[onclick="vote(${questaoId}, 1)"]`); const downBtn = document.querySelector(`button[onclick="vote(${questaoId}, -1)"]`); upBtn.classList.remove('active-up'); downBtn.classList.remove('active-down'); if (data.user_vote === 1) upBtn.classList.add('active-up'); if (data.user_vote === -1) downBtn.classList.add('active-down'); } }); }