Линейный поиск с барьером паскаль
Алгоритмы поиска в линейных структурах
Цель лекции: изучить основные алгоритмы поиска в линейных структурах и научиться решать задачи поиска в линейных структурах на основе алгоритмов последовательного и бинарного поиска .
Одним из важнейших действий со структурированной информацией является поиск . Поиск – процесс нахождения конкретной информации в ранее созданном множестве данных. Обычно данные представляют собой записи, каждая из которых имеет хотя бы один ключ . Ключ поиска – это поле записи, по значению которого происходит поиск . Ключи используются для отличия одних записей от других. Целью поиска является нахождение всех записей (если они есть) с данным значением ключа.
Структуру данных, в которой проводится поиск , можно рассматривать как таблицу символов (таблицу имен или таблицу идентификаторов) – структуру, содержащую ключи и данные, и допускающую две операции – вставку нового элемента и возврат элемента с заданным ключом. Иногда таблицы символов называют словарями по аналогии с хорошо известной системой упорядочивания слов в алфавитном порядке: слово – ключ , его толкование – данные.
Поиск является одним из наиболее часто встречаемых действий в программировании. Существует множество различных алгоритмов поиска, которые принципиально зависят от способа организации данных. У каждого алгоритма поиска есть свои преимущества и недостатки. Поэтому важно выбрать тот алгоритм , который лучше всего подходит для решения конкретной задачи.
Поставим задачу поиска в линейных структурах. Пусть задано множество данных, которое описывается как массив , состоящий из некоторого количества элементов. Проверим, входит ли заданный ключ в данный массив . Если входит, то найдем номер этого элемента массива, то есть, определим первое вхождение заданного ключа (элемента) в исходном массиве.
Таким образом, определим общий алгоритм поиска данных:
Шаг 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.
- Находится середина массива как частное от целочисленного деления количества элементов массива на 2. В данном случае получаем 5.
- Сравниваем элемент с пятым индексом с искомым элементом, т.е. сравниваем числа 16 и 8, если индексация идет с нуля. Они не равны друг другу, и 16 больше, чем 8.
- Находим середину левой части массива от пятого по индексу элемента. Для этого складываем индекс первого элемента и предыдущий от прежней середины. Если индексация идет с нуля, то получим 0+4 = 4. Далее делим нацело на 2, получаем 2 — это новая середина.
- Сравниваем второй по индексу элемент (число 7) и искомый (число 8). Они не равны и 7 меньше, чем 8.
- Значит рассматриваем отрезок начиная с третьего индекса до четверного. Его середина (3+4), деленная нацело на 2, равна 3.
- Сравниваем третий по индексу элемент с числом 8. Они равны. Значит искомый элемент есть в массиве и находится под третьим индексом.
Теперь рассмотрим ситуацию, когда элемента нет. Допустим требуется найти число 25 в том же массиве.
- Первая середина — число 16, что меньше 25-ти.
- Вторая середина — (6+10) / 2 = 8. 30 > 25.
- Третья середина — (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.