Algoritmo de pesquisa linear (Linear Search) em C++- explicação, exemplo e código

O algoritmo de busca linear é um método simples usado para encontrar um elemento específico em uma lista. Esse algoritmo funciona verificando sequencialmente cada elemento na lista até que o elemento desejado seja encontrado ou toda a lista seja percorrida.

Como funciona

1. Comece no primeiro elemento da lista.
2. Compare o elemento atual com o valor alvo.
3. Se o elemento atual for igual ao valor alvo, o algoritmo termina e retorna a posição do elemento.
4. Caso contrário, continue iterando pelos elementos restantes na lista.
5. Se toda a lista for percorrida sem encontrar o elemento de destino, o algoritmo retornará um valor indicando não encontrado.

Exemplo

Digamos que temos uma lista de números inteiros e queremos encontrar o número 34 na lista.

Lista: {12, 45, 67, 89, 34, 56, 23, 90}

1. Comece no primeiro elemento: 12. Não é o número desejado.
2. Mova para o próximo elemento: 45. Não é o número desejado.
3. Continue com os elementos restantes: 67, 89, 34. O elemento 34 corresponde ao número desejado.
4. O algoritmo termina e retorna a posição de 34, que é 4.

Exemplo de código em C++

#include <iostream>  
#include <vector>  
  
int linearSearch(const std::vector<int>& arr, int target) {  
    for(int i = 0; i < arr.size(); ++i) {  
        if(arr[i] == target) {  
            return i;  
        }  
    }  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 45, 67, 89, 34, 56, 23, 90};  
    int target = 34;  
  
    int result = linearSearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}  

No exemplo dado, usamos a linearSearch função para encontrar o número 34 na lista de inteiros. O resultado será a posição 34 na lista(as posições começam em 0) ou -1 se o número não for encontrado.