Gabarito disponível
Considere o código de busca binária abaixo, escrito em linguagem Python.
def busca_binaria(arr, low, high, x):
print("OK")
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return busca_binaria(arr, low, mid - 1, x)
else:
return busca_binaria(arr, mid + 1, high, x)
else:
return -1
arr = [5, 10, 30, 50, 70, 100, 120, 800]
resultado = busca_binaria(arr, 0, len(arr) - 1, 30)
Assim, a quantidade de vezes em que o string "OK" será impresso é igual a:
def busca_binaria(arr, low, high, x):
print("OK")
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return busca_binaria(arr, low, mid - 1, x)
else:
return busca_binaria(arr, mid + 1, high, x)
else:
return -1
arr = [5, 10, 30, 50, 70, 100, 120, 800]
resultado = busca_binaria(arr, 0, len(arr) - 1, 30)
Assim, a quantidade de vezes em que o string "OK" será impresso é igual a:
Resolução comentada
A busca binária por 30 faz 3 chamadas, então imprime 'OK' 3 vezes.
Chamada 1: low=0, high=7, mid=3 (50 > 30), logo high=2. Chamada 2: mid=1 (10 < 30), logo low=2. Chamada 3: mid=2 (30), que é o valor procurado, e a função retorna. Como 'OK' é impresso a cada chamada, são 3 vezes.
Análise das alternativas
A) 2 desconsidera a chamada em que o valor é encontrado. C, D e E) Contariam chamadas adicionais que não ocorrem, pois a busca termina ao achar o elemento.
Referência: Algoritmo de busca binária recursiva em Python.
Resolução comentada do VaiConcursos.