Линейный поиск в массивах.

[revizor]

Линейный поиск в массивах.

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

Вроде бы ничего сложного. Вот только не пойму почему в
среднем, следовательно, программа должна будет сравнить ключ поиска с
половиной элементов массива? Что значит с половиной?

Массив же придется весь просматривать, пока не найдется элемент (если он вообще есть). А не половину

[Stilet]

Что значит с половиной?

А то и значит что средняя вероятность найти искомое - 50%, т.е. чтоб его при такой вероятности найти придется просмотреть не менее половины массива.
Т.е. при запуске такой программы она "полюбому" (в среднем) пройдется по половине элементов, пока не найдет нужный.