Поиск одного элемента

Пример.Определить, есть ли в массиве элемент с заданным значением x, и, если он есть, найти его номер.

Если нет никакой информации о расположении элементов массива, то применяется линейный поиск, основная идея которого – последовательно просматривать массив, пока не будет обнаружено совпадение или не будет достигнут конец массива. Это реализует следующая простая программа:

Чтобы определить ситуацию, когда элемент не найден, нам надо ввести специальную переменную success, которая устанавливается в 1, если элемент найден, и остается равной нулю, если в массиве нет нужного элемента. Такая переменная называется флагом, флаг может быть установлен (равен 1) или сброшен (равен нулю).

Для линейного поиска в худшем случае мы имеем Nсравнений. Понятно, что для ускорения поиска надо сначала как-то упорядочить данные, в этом случае можно сделать поиск эффективным.