Faça um programa computacional que pergunte ao usuário 10 nomes próprios (sem sobrenomes), em ordem alfabética. O programa deve ser capaz de encontrar um nome e retornar a posição dele na lista. Caso o nome não seja encontrado, o programa deve retornar -1. Considere para a solução:
Busca binária.
Busca binária.
Passo 1
O enunciado pede um programa que receba do usuário uma lista de
nomes próprios ordenados alfabeticamente e, em seguida, busque um nome nessa lista usando busca binária, retornando sua posição (índice) ou
se não for encontrado. O conteúdo envolvido é manipulação de listas e o algoritmo de busca binária, que reduz o espaço de busca pela metade a cada passo.
Passo 2
Primeiro, vamos ler os
nomes em uma lista Python. Como o usuário deve digitar em ordem alfabética, não precisamos ordenar depois. Cada entrada será feita com
input()
e armazenada em names
.Passo 3
Em seguida, criamos a função
\(binary_search\)(arr, target)
que implementa a busca binária. A ideia é manter dois ponteiros, left
e right
, e repetir até left > right
:- Calcular
mid \(=\) (left \(+\) right) // \(2\)
. - Se
arr[mid] \(==\) target
, retornamid
. - Se
arr[mid] < target
, ajustarleft \(=\) mid \(+1\)
. - Caso contrário, ajustar
right \(=\) mid - \(1\)
.
Se não encontrar, retorna.
Passo 4
Depois de ler os
nomes, pedimos ao usuário o nome a buscar. Chamamos . Por fim, exibimos o resultado com
\(binary_search\)(names, target)
e recebemos a posição ou
print()
.Resposta
def \text{binary\_search}(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def main():
names = []
for i in range(10):
name = input(f"Digite o {i+1}\(\circ\) nome (ordenado alfabeticamente): ").strip()
names.append(name)
target = input("Digite o nome a buscar: ").strip()
position = \text{binary\_search}(names, target)
print(position)
if __name__ == "__main__":
main()