Линейный поиск
Линейный поиск проверяет элементы до совпадения или конца.
Что такое Линейный поиск?
Линейный поиск проверяет элементы до совпадения или конца.
Найдите цель в неотсортированных данных.
Важные моменты
- Проверяйте пустые, одиночные, повторяющиеся и отсортированные данные.
- Отделяйте корректность от оптимизации.
- В production предпочитайте стандартную библиотеку.
Визуализация: Линейный поиск
O(n)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Примеры кода на C и C++
main.c
#include <stdio.h>
int find(const int *values, int size, int target) {
for (int index = 0; index < size; ++index) {
if (values[index] == target) return index;
}
return -1;
}
int main(void) {
int values[] = {14, 3, 27, 8, 19};
printf("index=%d\n", find(values, 5, 8));
}
index=3C++
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector values{14, 3, 27, 8, 19};
auto match = std::find(values.begin(), values.end(), 8);
std::cout << "index="
<< std::distance(values.begin(), match) << '\n';
}
index=3Сравнение C и C++
Обе версии требуют O(n) в худшем случае. C возвращает -1, C++ — iterator, сравниваемый с end.
C
Циклы, указатели, длины и буферы задаются явно.
C++
Итераторы и алгоритмы отделяют операцию от хранения.
Практические задания
Запустите обе версии и изменяйте их, сравнивая гарантии языков.
- Проследите каждое сравнение.
- Проверьте дубликаты и крайние значения.
- Сравните со стандартной библиотекой.