Линейный поиск

  Основной вопрос задачи поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинство задач поиска сводится к простейшей — к поиску в массиве элемента с заданным значением. Рассмотрим именно эту задачу. Пусть требуется найти элемент Х в массиве А. В данном случае известно только значение разыскиваемого элемента, никакой дополнительной информации о нем или о массиве, в котором производится поиск, нет. Наверное, единственным способом является последоаательныйпросмотр массива и сравнение значения очередного рассматриваемого элемента массива с X. Напишем фрагмент:

For i:=1 To N Do If A[i]=X Then k:=i;

  В этом цикле находится индекс последнего элемента А, равного X, при этом массив просматривается полностью. А если требуется найти индекс первого элемента, равного X?

For i:=N DownTo 1 Do If A[i]=X Then k:=i;

А если исключить лишние проверки? Совпадение найдено, зачем делать "пустую" работу?

i:=I; While (i<=N) And (A[i]<>X) Do Inc(i); If i=N+l Then <X нет в A> Else <значение i указывает на место совпадениям>

  В этом фрагменте решается задача поиска первого совпадения. Для нахождения последнего совпадения требуется изменить совсем немного:

i:=N; While (i>0) And (A[i]<>X) Do Dec(i); If i=0 Then <X нет в A> Else <значение i указывает на место с6впадения>;

  Примечания.  1.Необходимо обратить внимание на порядок проверки составного условия цикла. Предполагается, что второе условие  не проверяется, если результат логического выражения определен после проверки первого условия. В противном случае возникает ошибка из-за выхода индекса за границы массива.                              2. Для контроля удобно использовать директиву {$R+).                              3. В качестве упражнения можно заменить цикл While на цикл Repeat ... Until.

  Вспомним технику использования "барьерных" элементов из темы "Сортировка" и применим ее для изучения поиска элемента в массиве. Это требует увеличения размерности массива А на единицу:

Type MyArray=Array[0..NMax] Of Integer;   или MyArray=Array[l..NMax+l) Of Integer; Var A:MyArray,

  Значение Nmax определяется в разделе констант. Найдем первое вхождение элемента Х в массив:

i:=l;A[N+l]:=Х; While A[i] <> X Do Inc(i); If i=N+l Then <X нет в A> Else <начение i указывает на место совпадения>;

  Для поиска последнего совпадения цикл записывается следующим образом (используем 1-й вариант описания массива А):

i:=N;A[0]:=Х; While A[i] <> X Do Dec(i); If i=0 Then <X нет в A> Else Оначение i указывает на место совпадения>;

  Очевидно, что число сравнений зависит от местонахождения искомого элемента. В среднем количество сравнений равно (N + 1) div 2, в худшем случае, когда элемента нет в массиве, N сравнений. Эффективность поиска — O(N).

Задания для самостоятельной работы

  1. Во входном файле дан массив А и массив из элементов, поиск которых будет осуществляться в массиве А. Изменить массив А таким образом, чтобы суммарное количество сравнений при поиске элементов было минимальным.

Примечание. По данным из второго массива формируются частоты поиска каждого элемента, и элементы массива А сортируются в порядке убывания значений этих частот ("метод перемещения в начало"). На основе этой задачи можно провести небольшое исследование. Необходимо найти значения N, при которых массивы не помещаются в оперативную память, отводимую под программу, или не помещаются и в "кучу". Если еще добавить и ограничения на время решения, то одного занятия для решения задачи может оказаться недостаточным.

  2. Даны массив А и число X.   Переставить элементы массива таким образом, чтобы вначале были записаны элементы, меньшие или равные X, а затем— большие или равные X.   Переставить элементы массива таким образом, чтобы вначале были записаны элементы, меньшие X, затем равные Х и, наконец, большие X.

  Примечание. Указанные перестановки следует сделать за один просмотр А и без использования дополнительных массивов.