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.

Passo 1

O enunciado pede um programa que receba do usuário uma lista de 10 nomes próprios ordenados alfabeticamente e, em seguida, busque um nome nessa lista usando busca binária, retornando sua posição (índice) ou -1 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 10 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, retorna mid.
  • Se arr[mid] < target, ajustar left \(=\) 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 \(binary_search\)(names, target) e recebemos a posição ou . Por fim, exibimos o resultado com 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()

Exercícios relacionados