Линейный поиск
Последнее обновление
Линейный поиск (его также называют последовательным поиском) - простейший алгоритм поиска: начните с первого элемента и сравнивайте каждый с целью, пока не найдёте совпадение или элементы не закончатся. Он не делает никаких предположений о данных: массив может быть неотсортированным, а элементами может быть что угодно, что можно сравнить на равенство.
Анимация выше подсвечивает каждое сравнение по мере того, как просмотр движется слева направо, и останавливается в момент появления цели. За простоту приходится платить скоростью: в худшем случае проверяется каждый элемент, поэтому алгоритм работает за O(n). Если данные отсортированы, бинарный поиск находит тот же ответ за O(log n), а если сначала нужны отсортированные данные, посмотрите сортировку слиянием.
Временная и пространственная сложность
| Случай | Сложность | Примечания |
|---|---|---|
| Лучший случай | O(1) | Первый элемент оказывается целью. |
| Средний случай | O(n) | В среднем до попадания проверяется половина элементов. |
| Худший случай | O(n) | Цель находится в конце, или её нет вовсе. |
| Память | O(1) | Хранится только текущий индекс. |
Шаг за шагом
| Шаг | Что происходит |
|---|---|
| 1 | Начните с индекса 0, первого элемента массива. |
| 2 | Сравните текущий элемент с целевым значением. |
| 3 | Если они равны, верните текущий индекс (найдено). |
| 4 | Иначе сдвиньтесь на одну позицию вправо и повторите. |
| 5 | Если конец массива достигнут без совпадения, цели нет (верните -1). |
Разобранный пример
Поиск 5 в [7, 3, 9, 1, 5, 8, 2]:
| Сравнение | Индекс | Элемент | Результат |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5: продолжаем просмотр. |
| 2 | 1 | 3 | 3 ≠ 5: продолжаем просмотр. |
| 3 | 2 | 9 | 9 ≠ 5: продолжаем просмотр. |
| 4 | 3 | 1 | 1 ≠ 5: продолжаем просмотр. |
| 5 | 4 | 5 | 5 = 5: найдено по индексу 4. |
Когда использовать линейный поиск
| Используйте, когда | Избегайте, когда |
|---|---|
| Данные не отсортированы или постоянно меняются | Данные отсортированы: бинарный поиск экспоненциально быстрее |
| Коллекция мала, и простота важнее | Набор данных большой и в нём ищут многократно |
| У вас есть только последовательный доступ (потоки, связные списки) | Вы можете позволить себе индекс или хеш-таблицу для поиска за O(1) |
Код Linear Search
Чистая, готовая к запуску реализация Linear Search на Python, JavaScript, Java, C++, C, Pseudocode. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Linear Search на Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))Код Linear Search на JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));Код Linear Search на Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}Код Linear Search на C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}Код Linear Search на C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}Код Linear Search на Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)Вопросы и ответы о линейном поиске
Какова временная сложность линейного поиска?
O(n) в среднем и худшем случаях (просмотру может понадобиться посетить каждый элемент) и O(1) в лучшем случае, когда первый элемент оказывается целью. Он использует O(1) дополнительной памяти.Нужны ли линейному поиску отсортированные данные?
Нет, в этом его главное преимущество. Линейный поиск работает с полностью неотсортированными данными, потому что проверяет каждый элемент на равенство; порядок не имеет значения. Бинарный поиск, напротив, работает только с отсортированными массивами.
Когда линейный поиск лучше бинарного?
O(n log n)), когда коллекция крошечная или когда доступ только последовательный, например поток или связный список. Для многократного поиска в отсортированных массивах выигрывает бинарный поиск.Линейный поиск - это то же самое, что последовательный поиск?
Да, оба названия описывают один и тот же алгоритм: просматривать элементы по порядку, пока цель не найдена или коллекция не закончилась.
Сколько сравнений линейный поиск делает в среднем?
n/2 сравнений; если цель отсутствует, то ровно n. Именно этот линейный рост дал алгоритму его название.Связанные ресурсы
Больше визуализаций
