MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-026

Enunciado: Sobre o algoritmo de busca binária iterativa a seguir:

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, se A[1] ≤ x < A[n], a comparação da linha 11 é executada pelo menos:

a) ⌊lg (n-1)⌋  vezes, para n ≥ 2
b) ⌊lg n⌋  vezes, para n ≥ 1
c) ⌈lg n⌉  vezes, para n ≥ 1
d) lg n + 1  vezes, para n ≥ 1
e) NDA

Ideia original de: Lucas Miguel de Carvalho