Организация таблицы идентификаторов в виде неупорядоченного массива записей. Метод линейного поиска

В этом случае добавление элементов в таблицу идентификаторов осуществляется в порядке их поступления. Поиск искомого элемента в такой таблице возможен только путем сравнения заданного значения идентификатора с идентификатором в каждой строке таблицы. Поиск прекращается, как только будет найден подходящий элемент, или будет достигнут конец таблицы. Для таблицы, содержащей n элементов, среднее ожидаемое число сравнений равно n/2, а максимальное число сравнений равно n. Время поиска Т_п в неупорядоченной таблице линейно зависит от количества содержащихся в ней элементов:

Т_п=О(n).

Отсюда происходит и название описанного метода – линейный поиск. Очевидно, что если количество элементов в таблице велико, то данный способ ее организации не является эффективным.