9796

Задача поиска. Линейный поиск (последовательный поиск)

Реферат

Информатика, кибернетика и программирование

Задача поиска Постановка задачи: Задан массив содержащий n фамилий. Необходимо определить существует ли в этом массиве заданная фамилия. Если существует, необходимо вывести её номер, иначе сообщить об её отсутствии. Линейный поиск (последовательный ...

Русский

2013-03-17

48.5 KB

12 чел.

Задача поиска

Постановка задачи: Задан массив содержащий n фамилий. Необходимо определить существует ли в этом массиве заданная фамилия. Если существует, необходимо вывести её номер, иначе сообщить об её отсутствии.

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

Будем предполагать, что каждый элемент массива уникален. Хотя, если это не так, то будем фиксировать только первое появление заданной строки в массиве.

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

Алгоритм

Const n=100; 

Type  strtype=string[20];

Var  m=array[1..n] of strtype;

  found:boolean; (* элемент найден *)

  i:integer; (* номер элемента *)

  str:string; (* искомая строка *)

== == == == == == == ==

i:=0;

repeat

inc(i);

found := m[i]=str;

until found or (i=n);

if found

then writeln(‘Номер искомой строки=’,i)

else writeln(‘В массиве нет заданной строки.');

== == == == == == == ==

Анализ алгоритма линейного поиска

В общем случае при поиске линейным методом среди n элементов требуется в среднем n/2 сравнений в случае успешного поиска и n сравнений в наихудшем случае (если в массиве нет искомого элемента).

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

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

Задан массив m состоящий из n элементов типа string. Необходимо найти номер элемента содержащего строку str.

Алгоритм бинарного поиска

В самом начале процесса поиска обозначим в переменной low=1 номер первого элемента массива, в переменной high=n номер последнего элемента массива.

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

Пример поиска 1

Поиск строки Chester.

Элемент Chesterнайден!

Пример поиска 2. Поиск строки Baker.

Элемент Baker НЕ найден!

Своим названием метод бинарного поиска обязан заложенной в него идеи «отсечения половины». Процесс последовательного деления пополам называется дихотомией, вследствие чего описанный метод поиска часто называют дихотомическим.

Текст программы

Program LEC3_5_4; {бинарный поиск}

const n=7;

Type

   diapason=1..n;

   MyArray=array[diapason] of string[20];

const

   m:MyArray=('Abel','Barnes','Bishop','Charles',

              'Chester','Davis','Fisher');

var

   str:string[20];

   low,high,test:diapason;

   found:boolean;

begin

 str:='Chester';

 {инициализация переменных}

 low:=1; high:=n; found:=false;

 {цикл поиска}

 while (not found) and (low <= high) do

 begin

   test:=(low + high) div 2;

   found:= m[test]=str;

   if m[test]>str

   then high:=test-1

   else low:=test+1;

 end; {while}

 if found

 then writeln('Строка '+str+' найдена. №=',test)

 else writeln('Строка '+str+' НЕ найдена!');

 writeln('Нажмите Enter...');   readln;

end.

Анализ алгоритма бинарного поиска

  1.  Для алгоритма бинарного поиска заданный массив должен быть предварительно упорядочен по возрастанию.
  2.  Число проверок для  массива из n элементов равно k=log2(n+1), где   – округление до ближайшего целого.

Число проверок при поиске

n

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

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

элемент
присутствует

элемент
отсутствует

элемент
присутствует

элемент
отсутствует

7

4

7

3

3

100

50

100

7

7

1 000

500

1 000

10

10

1 000 000

500 000

1 000 000

20

20


 

А также другие работы, которые могут Вас заинтересовать

74152. Административно-правовые гарантии прав граждан 17.37 KB
  Формы обращения граждан за защитой: предложение рекомендация гражданина по совершенствованию законов и иных нормативных правовых актов деятельности государственных органов и органов местного самоуправления развитию общественных отношений улучшению социально-экономической и иных сфер деятельности государства и общества; заявление представляет собой просьбу гражданина о содействии в реализации его конституционных прав и свобод или конституционных прав и свобод других лиц либо сообщение о нарушении законов и иных нормативных правовых...
74153. Понятие, особенности и виды административно-правового статуса гражданина РФ, иностранных граждан и лиц без гражданства 17.08 KB
  Структура административноправового статуса: административная правоспособность способность быть субъектом административного права иметь права и выполнять обязанности административноправового характера; административная дееспособность способность лица своими личными действиями приобретать субъективные права и выполнять обязанности а также нести ответственность в соответствии с нормами административноправового характера; совокупность прав и обязанностей; ответственность; гарантии реализации прав и обязанностей. Виды...
74154. Административно-правовой статус иностранных граждан и лиц без гражданства 18.26 KB
  Лицо без гражданства лицо не являющееся гражданином Российской Федерации и не имеющее доказательств наличия гражданства иностранного государства. Для пребывания иностранных граждан и лиц без гражданства на территории Российской Федерации существуют национальный режим и режим наибольшего благоприятствования. Иностранные граждане и лица без гражданства пользуются в Российской Федерации правами и несут обязанности наравне с гражданами Российской Федерации кроме случаев установленных федеральным законом или международными договорами РФ ч.
74155. Основные права и обязанности граждан в сфере государственного управления 16.36 KB
  Виды прав граждан в сфере государственного управления: на участие в управлении государством как непосредственно так и через своих представителей; на поступление на государственную службу; на обращение в органы государственной власти органы местного самоуправления и к их должностным лицам как индивидуально так и коллективно; на свободу передвижения; на неприкосновенность личности; на неприкосновенность жилища; на объединение включая право создавать профессиональные союзы для защиты своих интересов; на проведение собраний митингов...
74156. Административно-правовой статус юридических лиц 19.53 KB
  В отношении общественных организаций запрещаются создание объединений преследующих незаконные цели и осуществление деятельности посягающей на здоровье и нравственность населения права и законные интересы граждан. Обязанности юридических лиц: общие необходимость соблюдения требований законодательства в своей деятельности; обязанность государственной регистрации создания реорганизации ликвидации юридических лиц внесения изменений в уставные документы; специальные регистрация прав на недвижимое имущество и сделок с...
74160. Исследование эффективности автоматического отключения питания в системе TN-C 69 KB
  При отсутствии нулевого провода А 31 Выводы по разделам Обеспечивает ли защитное заземление защиту от косвенного прикосновения в системе TNC и почему Да защищает путём снижения тока кз отводом в землю Возможно ли автоматического отключение питания при отсутствии нулевого провода и почему Результаты измерений При целом нулевом проводе...