Pesquisar em uma lista de itens é uma ocorrência comum em ciência da computação. Existem dois algoritmos principais que você deve conhecer quando se trata de busca: linear search e binary search. A busca linear começa no início de uma lista e itera por cada item até encontrar o valor alvo que está procurando. Se o valor alvo for encontrado, o índice onde ele está localizado na lista é retornado. Se o valor alvo não for encontrado, -1 é retornado. Retornamos -1 porque não é um índice válido na maioria das linguagens de programação. Aqui está como o código fica para a busca linear:

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Se a lista que vamos pesquisar for [13, 4, 7, 9, 10] e o valor alvo for 9, a função retornaria 3 porque 9 está no índice 3. Se alterarmos o valor alvo para 5, a função retornaria -1 porque 5 não está na lista. Embora este seja um algoritmo relativamente simples, ele não é o mais eficiente. Se você tem uma lista grande de itens, a busca linear pode levar muito tempo para encontrar o valor alvo. A complexidade de tempo da busca linear é O(n) porque o tempo que leva para pesquisar na lista cresce linearmente com o tamanho da lista. A complexidade de espaço da busca linear é O(1) porque não requer espaço adicional para percorrer a lista. A busca binária é um algoritmo mais eficiente para pesquisar em uma grande lista de itens. A condição aqui é que a lista deve estar ordenada em ordem crescente. A busca binária funciona dividindo a lista ao meio e verificando se o valor alvo está no meio da lista. Se o valor alvo estiver no meio da lista, o índice do valor alvo será retornado. Caso contrário, o algoritmo verifica se o valor alvo está na metade esquerda ou direita da lista. Ele continua a dividir as partes restantes da lista em metades até que o valor alvo seja encontrado. Se o valor alvo não estiver na lista, ele retorna -1 Aqui está como o código fica para busca binária:

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2  

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Começamos identificando um índice low e high. Isto representa o intervalo da lista que estamos pesquisando. Em seguida, verificamos a condição de low ser menor ou igual a high. Se low for maior que high, já pesquisamos por toda a lista e o valor alvo não foi encontrado. Nesse caso, paramos a busca e retornamos -1. Se o índice low for menor ou igual ao índice high, calculamos o índice do meio da lista, mid. Em seguida, verificamos se o valor alvo está no índice do meio. Se for, retornamos o índice do meio. Caso contrário, verificamos se o valor no ponto médio é menor que o alvo. Se for, atualizamos o índice baixo para ser o índice do meio mais um. Isso significa que vamos buscar a metade direita da lista. Por fim, se nenhuma das outras condições for True, atualizamos o índice high para ser o índice do meio menos um. Isso significa que iremos buscar na metade esquerda da lista. Continuamos a repetir esse processo até encontrarmos o alvo ou determinarmos que o alvo não está na lista. A complexidade de tempo da busca binária é O(log n) porque o tempo que leva para buscar na lista cresce logaritmicamente com o tamanho da lista. A complexidade de espaço da busca binária é O(1) porque não requer espaço adicional para percorrer a lista. A busca binária e a busca linear podem ser usadas para uma variedade de problemas que você encontrará em ciência da computação. É importante entender as diferenças entre os dois algoritmos e quando usar cada um.