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:

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        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:

function binarySearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (arr[mid] === target) {
            return mid;
        } else if (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.