Линейный поиск с барьером паскаль

Алгоритмы поиска в линейных структурах

Цель лекции: изучить основные алгоритмы поиска в линейных структурах и научиться решать задачи поиска в линейных структурах на основе алгоритмов последовательного и бинарного поиска .

Одним из важнейших действий со структурированной информацией является поиск . Поиск – процесс нахождения конкретной информации в ранее созданном множестве данных. Обычно данные представляют собой записи, каждая из которых имеет хотя бы один ключ . Ключ поиска – это поле записи, по значению которого происходит поиск . Ключи используются для отличия одних записей от других. Целью поиска является нахождение всех записей (если они есть) с данным значением ключа.

Структуру данных, в которой проводится поиск , можно рассматривать как таблицу символов (таблицу имен или таблицу идентификаторов) – структуру, содержащую ключи и данные, и допускающую две операции – вставку нового элемента и возврат элемента с заданным ключом. Иногда таблицы символов называют словарями по аналогии с хорошо известной системой упорядочивания слов в алфавитном порядке: слово – ключ , его толкование – данные.

Поиск является одним из наиболее часто встречаемых действий в программировании. Существует множество различных алгоритмов поиска, которые принципиально зависят от способа организации данных. У каждого алгоритма поиска есть свои преимущества и недостатки. Поэтому важно выбрать тот алгоритм , который лучше всего подходит для решения конкретной задачи.

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

Таким образом, определим общий алгоритм поиска данных:

Шаг 1. Вычисление элемента, что часто предполагает получение значения элемента, ключа элемента и т.д.

Шаг 2. Сравнение элемента с эталоном или сравнение двух элементов (в зависимости от постановки задачи).

Шаг 3. Перебор элементов множества , то есть прохождение по элементам массива.

Основные идеи различных алгоритмов поиска сосредоточены в методах перебора и стратегии поиска.

Рассмотрим основные алгоритмы поиска в линейных структурах более подробно.

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

Последовательный (линейный) поиск – это простейший вид поиска заданного элемента на некотором множестве, осуществляемый путем последовательного сравнения очередного рассматриваемого значения с искомым до тех пор, пока эти значения не совпадут.

Идея этого метода заключается в следующем. Множество элементов просматривается последовательно в некотором порядке, гарантирующем, что будут просмотрены все элементы множества (например, слева направо). Если в ходе просмотра множества будет найден искомый элемент, просмотр прекращается с положительным результатом; если же будет просмотрено все множество, а элемент не будет найден, алгоритм должен выдать отрицательный результат.

Алгоритм последовательного поиска

Шаг 1. Полагаем, что значение переменной цикла i=0 .

Шаг 2. Если значение элемента массива x[i] равно значению ключа key , то возвращаем значение , равное номеру искомого элемента, и алгоритм завершает работу. В противном случае значение переменной цикла увеличивается на единицу i=i+1 .

Линейный поиск с барьером паскаль

Примеры поиска : поиск требуемого элемента в базе данных (телефонный справочник); поиск вхождения одного фрагмента текста в другой (сравнение двух текстов, антиреферат, поиск плагиата) и т.д. Результат поиска как правило булевский, или указание места расположения элемента.

Простейший алгоритм поиска — линейный. Эталонный массив просматривается последователь-но от первого до последнего элемента.

Наихудший случай — слова нет в массиве (не найдено) – вывод можно сделать после просмотра всего массива.

Достоинство – простота реализации. Недостаток – большое время.

Если используется for всегда выполняется ровно n операций сравнения, независимо от того, найдено слово или нет. Разумно прекращать поиск если, слово найдено (если не требуется найти все вхождения слова).

При равномерном распределении элементов в массиве среднее время поиска обычно пропор-ционально величине n/2.

Во всех ниже изложенных алгоритмах будем считать, что производится поиск в массиве A из N целых чисел элемента, равного X.

Различают первое вхождение элемента в список, последнее вхождение, все вхождения.

ПОИСК С БАРЬЕРОМ

Идея поиска с барьером : не проверять каждый раз в цикле условие достижения границы мас-сива.

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

Достоинство: на одну проверку меньше в цикле.

Выход из цикла, в котором теперь остается только условие поиска, может произойти либо на найденном элементе, либо на барьере. Таким образом, после выхода из цикла проверяется, не барьер ли мы нашли?

Вычислительная сложность поиска с барьером меньше, чем у линейного поиска, но имеет тот же порядок.

Существует два способа установки барьера: дополнительный элемент или вместо крайнего элемента массива.

ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК

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

Так при поиске числа с заданным значением необходимо иметь массив, упорядоченный по воз-растанию или по убыванию значений элементов. А, например, при поиске числа с заданной суммой цифр массив должен быть упорядочен по возрастанию или по убыванию сумм цифр элементов.

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

Существуют две модификации этого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент: округлением в меньшую или большую сторону. В первом случае средний элемент относится к левой части массива, а во втором — к правой.

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

Предполагается, что массив упорядочен по величинам ключей элементов.

Идея алгоритма: предполагается равномерное распределение величин в некотором их диапазо-не от u до l. Поэтому, зная величину Х ключа поиска, можно предсказать более точное положе-ние искомой записи, чем просто в середине некоторого отрезка файла. Интерполяционный по-иск ассимптотически предпочтительнее бинарного.

Алгоритм основан на формуле i=l+trunc((u-l)*(X-K[l])/(K[u]-K[l]))

Время t работы алгоритма оценивается формулой: t=a*logN

ПОИСК минимума и максимума

При поиске минимума или максимума используют дополнительную переменная min (или max):

1) промежуточной переменной присваивается значение первого числа из последовательности, т.е. принимается, что первое число является текущим минимумом (максимумом);

2) начиная со второго числа, производится сравнение этого числа со значением переменной min (или max) и если число из массива меньше min (больше max), то на место min (max) записыва-ется это число. Теперь это число будет текущим минимумом (максимумом);

После просмотра всех чисел в переменной min (или max) будет находиться окончательное зна-чение минимума (или максимума).

Поиск

Пусть дан массив элементов A и ключ b. Для b необходимо найти совпадающий с ним элемент массива А. Линейный поиск подразумевает последовательный просмотр всех элементов массива А в порядке их расположения, пока не найдется элемент равный b. Если заранее неизвестно, имеется данный элемент в массиве или нет, то необходимо следить за тем, чтобы поиск не вышел за границы массива, что достигается использованием стоппера (барьерного элемента). Рассмотрим 2 примера:

1)без использования стоппера

var A:array[0..N-1] of Any;

writeln(‘Введите элементы массива:’);

for i:=0 to N-1 do

while (i<>N) and (A[i]<>b) do

writeln(‘Элемент, совпадающих с ключом, найден. Позиция элемента -‘,i+1)

writeln(‘Элементов, совпадающих с ключом, нет’);

2) с использованием стоппера

var A:array[0..N] of Any;

writeln(‘Введите элементы массива:’);

for i:=0 to N-1 do

writeln(‘Элемент, совпадающих с ключом, найден. Позиция элемента -‘,i+1)

writeln(‘Элементов, совпадающих с ключом, нет’);

Следует отметить, что в общем случае при линейном поиске среди N элементов требуется в среднем N/2 сравнений в случае успешного поиска и N сравнений в наихудшем случае, и затраты времени для больших массивов поэтому велики.

Применяется данный алгоритм, если никакой дополнительной информации о данных массива нет.

Бинарный поиск

Очевидно, что нельзя каким-либо способом ускорить поиск, если отсутствует информация о данных, среди которых производится поиск. Также известно, что если данные упорядочены, то поиск можно сделать значительно эффективнее. Поэтому рассмотрим алгоритм, который основан на том, что массив A упорядочен (т. е. a[i-1]

Суть: берут средний элемент массива и сравнивают его с ключом. В результате возможны 3 случая:

1) если элемент массива равен ключу, то искомый элемент найден;

2)если элемент массива меньше ключа, то все элементы массива с индексами, которые меньше N/2 исключаются из рассмотрения;

3)если элемент массива больше ключа, то все элементы массива с индексами, которые больше N/2 исключаются из рассмотрения;

Затем поиск продолжается в одной из половин массива аналогичным образом.

var A:array[0..N] of Any;

writeln(‘Введите упорядоченную последовательность эл-тов массива ‘);

for i:=0 to N do readln(A[i]);

m:=(Left+Right) div 2;

if (Right<>N) or ((Right=N) and (a[N]=b)) then

writeln(‘ Эл — т найден . Позиция эл-та: ‘,Right)

writeln(‘ Элемента нет ‘);

Нахождение элемента бинарным поиском осуществляется очень быстро. При поиске среди N элементов требуется log2(N) сравнений в наихудшем случае. Кроме того, бинарный поиск уже при N порядка 100 значительно эффективнее линейного — как по скорости обнаружения, так и по способности к получению отрицательного результата. Для доказательства этого приведу следующие характеристики линейного и бинарного поиска:

1) линейный поиск:

среднее количество сравнений при наличии элемента:5

количество сравнений при отсутствии элемента:10

среднее количество сравнений при наличии элемента:500

количество сравнений при отсутствии элемента:1000

среднее количество сравнений при наличии элемента:500000

количество сравнений при отсутствии элемента:1000000

1) бинарный поиск:

максимальное количество сравнений при наличии элемента:8

максимальное количество сравнений при отсутствии элемента:8

максимальное количество сравнений при наличии элемента:10

максимальное количество сравнений при отсутствии элемента:10

максимальное количество сравнений при наличии элемента:20

максимальное количество сравнений при отсутствии элемента:20

Интерполяционный поиск

Представим себе поиск слова в словаре. Маловероятно, что мы сначала заглянем в середину словаря, затем отступим от начала на 1/4 или 3/4 и т.д, как в бинарном поиске.

Если нужное слово начинается с буквы ‘А’, то и поиск имеет смысл начинать в начале словаря. Когда же найдена отправная точка для поиска, дальнейшие действия будут мало похожи на рассмотренные выше методы.

Мы приходим к алгоритму, называемому интерполяционным поиском. Пусть задан массив записей R1,R2. Rk, снабженных соответственно ключами K1,K2. Kn. Необходимо найти запись с данным ключом K. Тогда, если известно, что K лежит между Kl и Ku, то следующую пробу делаем примерно на расстоянии (u-l)*(K-Kl)/(Ku-Kl) от l, предполагая, что ключи являются числами, возрастающими приблизительно как арифметическая прогрессия.

Интерполяционный поиск требует в среднем около log2 log2 N шагов, и поэтому он предпочтительнее бинарного при работе с большими массивами.

Поиск подстроки в строке.

Пусть дана строка s и подстрока p. Тогда для поиска подстроки p в строке s возможно использование следующего алгоритма:

until (j=lp) or (i=lp-ls) or (i>ls);

if (j=lp) and (lp<>1) then writeln(‘ Подстрока в строке есть ‘);

if i<>ls then writeln(‘ Подстроки в строке нет ‘);

Алгоритм является эффективным, если несовпадение символов строки и подстроки происходит после нескольких сравнений во внутреннем цикле. Но, если совпадение обнаружено в конце строки, то требуется lp*ls сравнений.

Алгоритм Кнута, Морриса и Пратта (КМП)

Этот алгоритм был создан в 1970 году и получил свое название от имен его разработчиков. Он состоит из двух этапов: подготовительного и основного.

На подготовительном этапе учитывается структура подстроки. Для этого формируется массив D, в котором учитывается совпадения символов подстроки с началом подстроки следующим образом: нулевой элемент массива D получает значение равное -1. Далее для каждой позиции j, совпадающей с началом подстроки, вычисляется максимальное количество предшествующих ей символов. Если же совпадений нет, то соответствующий элемент массива D равен -1. Размерность массива D равна длине подстроки.

Теперь рассмотрим основной этап. Поиск начинается со сравнения первого символа строки с первым символом подстроки. В случае несовпадения происходит сдвиг подстроки на количество символов, указанных соответствующим элементом массива D. Если совпадения подстроки со строкой не будет (то есть данной подстроки в строке нет), то программа выйдет из цикла для поиска подстроки, когда i будет равняться длине строки, то есть если ни один символ подстроки не совпадает ни с одним символом строки, то программа выполнит N сравнений, если же совпадения отдельных элементов подстроки(но не всей подстроки со строкой) будут найдены, то в наихудшем случае потребуется N+M сравнений. Если же совпадение подстроки со строкой обнаружится сразу, то потребуется M cравнений.

Функция бинарного поиска в массиве

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

Двоичный (бинарный) поиск элемента в массиве применим только к отсортированному массиву. Рассмотрим, как осуществляется бинарный поиск в отсортированном по возрастанию массиве.

Допустим, есть массив чисел [1, 3, 7, 8, 15, 16, 19, 20, 30, 32]. Требуется определить, есть ли в нем элемент со значением 8.

1. Находится середина массива как частное от целочисленного деления количества элементов массива на 2. В данном случае получаем 5.
2. Сравниваем элемент с пятым индексом с искомым элементом, т.е. сравниваем числа 16 и 8, если индексация идет с нуля. Они не равны друг другу, и 16 больше, чем 8.
3. Находим середину левой части массива от пятого по индексу элемента. Для этого складываем индекс первого элемента и предыдущий от прежней середины. Если индексация идет с нуля, то получим 0+4 = 4. Далее делим нацело на 2, получаем 2 — это новая середина.
4. Сравниваем второй по индексу элемент (число 7) и искомый (число 8). Они не равны и 7 меньше, чем 8.
5. Значит рассматриваем отрезок начиная с третьего индекса до четверного. Его середина (3+4), деленная нацело на 2, равна 3.
6. Сравниваем третий по индексу элемент с числом 8. Они равны. Значит искомый элемент есть в массиве и находится под третьим индексом.

Теперь рассмотрим ситуацию, когда элемента нет. Допустим требуется найти число 25 в том же массиве.

1. Первая середина — число 16, что меньше 25-ти.
2. Вторая середина — (6+10) / 2 = 8. 30 > 25.
3. Третья середина — (6+7) / 2 = 6 (деление нацело). 19 Pascal

const N = 20 ;
type arr = array [ 1 .. N ] of integer ;
var
a : arr ;
i : byte ;
p , q , e : integer ;

function search ( var c : arr ; elem : integer ) : byte ;
var m , i , j : integer ;
begin
m : = N div 2 ;
i : = 1 ;
j : = N ;
while ( c [ m ] <> elem ) and ( i c [ m ] then i : = m + 1
else j : = m — 1 ;
m : = ( i + j ) div 2 ;
end ;
if i > j then search : = 0
else search : = m ;
end ;

begin
randomize ;
p : = 1 ;
q : = 4 ;
for i : = 1 to N do begin
a [ i ] : = random ( q — p ) + p ;
p : = p + 3 ;
q : = q + 3 ;
write ( a [ i ] , ‘ ‘ ) ;
end ;
writeln ;
write ( ‘Число: ‘ ) ;
readln ( e ) ;
i : = search ( a , e ) ;
if i = 0 then
writeln ( ‘Такого числа в массиве нет.’ )
else
writeln ( ‘Число ‘ , e , ‘ находится на ‘ , i , ‘-м месте.’ ) ;
end .

1 6 7 11 15 17 19 23 27 28 31 35 38 40 45 48 50 52 56 59
Число: 43
Такого числа в массиве нет.

1 5 7 10 14 18 20 23 25 29 33 36 38 41 45 48 51 54 57 58
Число: 25
Число 25 находится на 9 -м месте.

Линейный поиск с барьером паскаль

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

Задача 1.

В первой строке задается одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке содержатся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000). В третьей строке вводится одно целое число x, не превосходящее по модулю 1000. Вывести значение элемента массива, ближайшее к x. Если таких чисел несколько, выведите любое из них.

Число А называется ближайшим к Х , если модуль разности А-Х наименьший (|A-Х|). Если два числа будут находиться в одинаковой близости к числу Х, будем брать любой из них. В условии так и сказано.

Когда решали задачу на нахождение максимального элемента массива, мы задавали «точку отсчета» (назову ее так), т.е. принимали первый элемент массива за максимальный. В этой задаче мы поступим аналогично, но таких «точек отсчета» будет две: 1. минимальный модуль разности; 2. Ближайший элемент массива.

Рассмотрим код программы (Паскаль):

В программе переменная raz отвечает за минимальный модуль разности — Первая «Точка отсчета», min — ближайший элемент массива к заданному числу X, вторая «Точка отсчета».

Если найдется такой элемент массива, начиная со второго, который окажется меньше чем «точка отсчета», переменные raz и min переопределятся.

Задача 2.

В связи с визитом Императора Палпатина было решено обновить состав дроидов в ангаре 32. Из-за кризиса было решено новых дроидов не закупать, но выкинуть пару старых. Как известно, Палпатин не переносит дроидов с маленькими серийными номерами, так что все, что требуется — найти среди них двух, у которых серийные номера наименьшие.

Формат входного файла

Первая строка входного файла содержит целое число N – количество дроидов. (2 ≤ N ≤ 1000), вторая строка – N целых чисел, по модулю не превышающих 2*10 9 – номера дроидов

Формат выходного файла

Выведите два числа: первым – последний по величине из номеров дроидов (такого следует утилизировать в первую очередь), а вторым – предпоследний.

После задания массива, состоящего из n элементов, мы проверяем: первый или второй элемент массива меньше. Это и есть наша «точка отсчета». Минимальный элемент — min. Min2 — элемент, стоящий после min (по условию задачи).

Далее, в цикле от 3 до n мы проверяем: если элемент массива меньше чем min, то в переменную min2 мы записываем старое значение переменной min и переопределяем ее min:=mas[i]. Если это условие не выполняется (элемент массива больше min), мы проверим, может быть этот элемент меньше нашего второго значения min2.