Алгоритм линейного поиска (Linear Search) в C++ — объяснение, пример и код

Алгоритм линейного поиска — это простой метод, используемый для поиска определенного элемента в списке. Этот алгоритм работает путем последовательной проверки каждого элемента в списке до тех пор, пока не будет найден нужный элемент или не будет пройден весь список.

Как это работает

1. Начните с первого элемента в списке.
2. Сравните текущий элемент с целевым значением.
3. Если текущий элемент равен целевому значению, алгоритм завершает работу и возвращает позицию элемента.
4. Если нет, продолжайте перебирать оставшиеся элементы в списке.
5. Если весь список пройден, но целевой элемент не найден, алгоритм возвращает значение, указывающее, что он не найден.

Пример

Допустим, у нас есть список целых чисел, и мы хотим найти число 34 в списке.

Список: {12, 45, 67, 89, 34, 56, 23, 90}

1. Начните с первого элемента: 12. Не нужное число.
2. Перейти к следующему элементу: 45. Не нужное число.
3. Продолжайте с оставшимися элементами: 67, 89, 34. Элемент 34 соответствует нужному номеру.
4. Алгоритм завершается и возвращает позицию 34, то есть 4.

Пример кода на С++

#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;  
}  

В данном примере мы использовали linearSearch функцию, чтобы найти число 34 в списке целых чисел. Результатом будет позиция 34 в списке(позиции начинаются с 0) или -1, если номер не найден.