1. Основные понятия алгоритмизации и программирования

9.2. Постановка задачи поиска

В практической деятельности приходится решать такие прикладные задачи, в которых необходимо локально или автономно произвести поиск нужных объектов. Рассмотрим задачу поиска элемента в массиве.
Пусть задан массив, состоящий из одного или нескольких элементов любого типа, отличного от файлового. Предположим, что в некотором массиве хранится множество из n (n × m) элементов и необходимо определить положение некоторого элемента в этом массиве. Каждый элемент массива имеет индекс (индексы), причем индексы различны и однозначно идентифицируют элементы массива.
Задача поиска в этом случае состоит в отыскании индекса (индексов) элемента по заданному свойству элемента.
Существуют два возможных результата поиска:

• 
  поиск оказался удачным, т.е. позволил определить положение элемента в массиве;
  
• 
  поиск оказался неудачным, т.е. достигнут конец массива, но элемент с заданным свойством отсутствует.
  

9.3. Последовательный (линейный) поиск

Простейшим методом поиска является последовательный просмотр таблицы, одномерного массива или строки до нахождения элемента с требуемыми свойствами или установления факта, что такого элемента нет. Для массива, данные в котором не упорядочены сортировкой, единственный путь поиска заданного элемента состоит в сравнении каждого элемента массива с заданным. При совпадении некоторого элемента массива с заданным, его позиция в массиве фиксируется. Этот алгоритм называется последовательным, или линейным, поиском. Ядром такого алгоритма является цикл по индексу массива. Так, если в массиве int a[n] нужно найти введенное с клавиатуры целое число х, о котором никакой дополнительной информации нет, то соответствующий цикл можно записать следующим образом:
for (i = 0; i < n; i++) if (a[i] == x) k = i;
Этот способ решения обладает двумя существенными недостатками:

• 
  если значение х встречается в массиве несколько раз, то будет найдено последнее из них;
  
• 
  после того, как нужное значение уже найдено, массив просматривается до конца, то есть всегда выполняется n сравнений.
  

Для устранения этих недостатков необходимо прервать просмотр массива сразу после обнаружения заданного числа. Так как в этом случае число повторений не известно, необходимо использовать цикл с предусловием:
while ((i < n) && (a[i] != x)) i++;