Линейный поиск

Линейный поиск (также известный как последовательный поиск) — это самый простой алгоритм поиска. Он заключается в последовательном просмотре каждого элемента списка до тех пор, пока не будет найден искомый элемент или не будет достигнут конец списка.

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

Алгоритм линейного поиска работает следующим образом:

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

Псевдокод

Вот псевдокод для алгоритма линейного поиска:

``` function linearSearch(arr, target) {

   for (i = 0; i < arr.length; i++) {
       if (arr[i] == target) {
           return i;  // Элемент найден, вернуть индекс
       }
   }
   return -1;  // Элемент не найден

} ```

Пример

Давайте рассмотрим пример поиска числа `22` в массиве `[10, 50, 30, 70, 80, 60, 20, 90, 40]`:

1. Начинаем с первого элемента (`10`).
2. Сравниваем `10` с `22` - не совпадает.
3. Переходим к следующему элементу (`50`).
4. Сравниваем `50` с `22` - не совпадает.
5. ...
6. Переходим к элементу `20`.
7. Сравниваем `20` с `22` - не совпадает.
8. Переходим к элементу `90`.
9. Сравниваем `90` с `22` - не совпадает.
10. Переходим к элементу `40`.
11. Сравниваем `40` с `22` - не совпадает.
12. Достигнут конец массива, элемент не найден. Возвращаем `-1`.

Временная сложность

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

• Лучший случай: $O(1)$ (элемент найден в начале списка).
• Средний случай: $O(n)$
• Худший случай: $O(n)$ (элемент не найден или находится в конце списка).

Преимущества и недостатки

Преимущества:

• Прост в реализации.
• Не требует предварительной сортировки списка.
• Эффективен для небольших списков или когда нужно найти элемент, который, вероятно, находится в начале списка.

Недостатки:

• Неэффективен для больших списков, так как требует просмотра каждого элемента в худшем случае.

Когда использовать

Линейный поиск полезен в следующих случаях:

• Когда список небольшой.
• Когда порядок элементов не важен и список не отсортирован.
• Когда нужно найти элемент, который, вероятно, находится в начале списка.

В остальных случаях более эффективные алгоритмы поиска, такие как бинарный поиск (для отсортированных списков), будут предпочтительнее.