Что делает линейный поиск
Линейный (последовательный) поиск — простейший алгоритм нахождения элемента в массиве. Он перебирает элементы один за другим, сравнивая каждый с искомым значением, пока не найдёт совпадение или не дойдёт до конца. Никакой предварительной сортировки не требуется, дополнительных структур данных тоже.
Алгоритм выполняет не более n сравнений, где n — длина массива. В худшем случае (элемент отсутствует или стоит последним) просматриваются все n элементов. В лучшем — достаточно одного сравнения, если искомое значение стоит в начале.
Базовая реализация
C:
#include <stdio.h>
/*
* Возвращает индекс первого вхождения target в массив arr
* длины n. Если элемент не найден, возвращает -1.
*/
int linear_search(const int *arr, int n, int target)
{
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
int main(void)
{
int data[] = {4, 2, 7, 1, 9, 3};
int n = (int)(sizeof(data) / sizeof(data[0]));
int result = linear_search(data, n, 7);
if (result != -1) {
printf("Элемент найден на позиции %d\n", result);
} else {
printf("Элемент не найден\n");
}
return 0;
}Вывод программы:
Код:
Элемент найден на позиции 2Разбор по шагам
- Функция получает указатель на начало массива, его длину и искомое значение.
- Цикл
forпроходит от индекса0доn - 1.
- На каждой итерации
arr[i]сравнивается сtarget.
- При совпадении функция немедленно возвращает текущий индекс.
- Если цикл завершился без совпадения, возвращается
-1— сигнал «не найдено».
Возврат
-1 безопасен, потому что в C индексы массива всегда неотрицательны. Это общепринятое соглашение для функций поиска.Поиск всех вхождений
Базовая версия останавливается на первом совпадении. Если нужно собрать все позиции, где встречается значение, функция...