Pergunta da semana do dia 26/03 - 1ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Sobre o algoritmo da PESQUISA-BINÁRIA-ITERATIVA:

BINARY-SEARCH(A, x)

1  if x < A[1] then
2     return 0
3  if x ≥ A[n] then
4     return n
5  // aqui A[1] ≤ x < A[n]
6  start ← 1
7  end ← n
8  // invariante: A[start] ≤ x < A[end]
9  while start + 1 < end do
10    middle ← (start + end)/2
11    if A[middle] ≤ x then
12       start ← middle
13    else
14       end ← middle
15 return start

é correto afirmar que a comparação da linha 11 é executada pelo menos :

a) ⌊lg n⌋  vezes
b) ⌊n/2⌋ vezes
c) ⌈(n+1)/2⌉ vezes
d) lg n +1  vezes
e) NDA



Ideia original de: Lucas Miguel de Carvalho