Лабораторная работа Тема: Линейный поиск

1-Лабораторная работа
Тема: Линейный поиск
Цель работы. Изучит и реализовать алгоритм линейного поиска.
Теоритический част.
Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Даный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию.
Алгоритм
Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.
отрезок имеет длину N, то найти решение с точностью до ε можно за время . Т.о. асимптотическая сложность алгоритма — O(). В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.
Реализация двоичного поиска на С++
В качестве примера можно рассмотреть поиск значения функции на множестве целых чисел, представленной таблично.
Переменные L и R содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются с первого элемента отрезка. Если искомое значение не равно значению функции в данной точке, то осуществляется переход к следующей точке. Т.о., в результате каждой проверки область поиска уменьшается на один элемент.

1-задание

Вам задается одномерный массив и число k . Ваша задача состоит из нахождение всех вхождение заданного числа в массиве.
Входные данные
В первой строке задается целое число – количество элементов массива (1≤n≤100). Во второй строке задаеться n  числа –  элменты массива. В трети строке задается число k.
Выходные данные
В первой строке выведите количество вхождении. Во второй строке выведите индексов вхождении в возрастающем порядке.

#include using namespace std; struct mass{ int x, y; } a[102]; int main(){ int n; cin >> n; for(int i = 1; i <= n; i++ ){ cin >> a[i].x; a[i].y = i; } int k; cin >> k; int cnt = 0; for( int i = 1; i <= n; i++){ if(a[i].x == k ){ cnt++;}} cout << cnt << endl; for(int i = 1; i <= n; i++){ if(a[i].x == k ){ cout << a[i].y << " "; }} }