Алгоритм линейного поиска

Работа алгоритма заключается в том, что элементы массива, начиная с первого, последовательно сравнивается с искомым элементом. Сравнение элементов продолжается до тех пор, пока не будут просмотрены все элементы или очередной элемент массива не равен искомому.

 

Алгоритм быстрого линейного поиска

Любой алгоритм поиска содержит блок проверки на окончание массива. В алгоритме линейного поиска эта проверка осуществляется каждый раз перед обращением к очередному элементу. Однако проверка на окончание массива может осуществляться не при каждом сравнении. Для этого в конец массива включается (N + 1)-й элемент (N — количество элементов в массиве), равный искомому. Тогда проверка на окончание массива осуществляется лишь при совпадении очередного элемента с искомым. Если этот элемент находится внутри массива, то поиск заканчивается удачно и элемент считается найденным. Если же этот элемент оказался (N + 1)-ым, то искомого элемента в массиве нет.