11. Последователно търсене [4, стр. 231]


** Човешката дейност търсене

** Опростен модел на търсене

** Фундаментални операции над елемнтите на множество (правилна оценка на ефективността на алгоритмите за търсене)
-- инициализиране
-- търсене
-- вмъкване
-- изтриване
-- обединяване на множества
--  сортиране.

** Ключ, повтарящи се ключове
-- има ли елемент с даден ключ? [bool exists(unsigned key)]
-- индекс на елемент (обект) с даден ключ? [unsigned find_one(unsigned key)]
-- брой елементи с даден ключ? [unsigned count(unsigned key)]
-- индекси на всички елементи (обекти) с даден ключ? [vector<unsigned> find_all(unsigned key)]

** Последователно (линейно) търсене
Проверяваме последователно елементите на множеството (което е линейно наредено), докато или намерим търсения елемент или стигнем до края на редицата.
Ефективност на алгоритъма за линейно търсене:
Броят на обръщенията към елементите на масива зависи от търсеното число, но в най-лошия случай, когато числото не се среща в масива, е равен на дължината на масива. Следователно сложността на алгоритъма е O(n).

** Последователно търсене в сортиран списък с поддържане на сортирания списък при вмъкване на нов елемент.

** Последователно търсене с преподреждане
Задача 11. Words search