9796

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

Реферат

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

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

Русский

2013-03-17

48.5 KB

13 чел.

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

Постановка задачи: Задан массив содержащий 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


 

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

80420. Изучение особенностей адаптации к роли матери у женщин, имеющих детей разного возраста 731.5 KB
  Важность материнского поведения для развития ребенка его сложная структура и путь развития множественность культурных и индивидуальных вариантов а также огромное количество современных исследований в этой области позволяют говорить об особой актуальности изучения материнства...
80421. ОРГАНІЗАЦІЯ ТА ОБЛІК РОЗРАХУНКІВ З ОПЛАТИ ПРАЦІ (НА МАТЕРІАЛАХ СІЛЬСЬКОГОСПОДАРСЬКИХ ПІДПРИЄМСТВ БЕРЕЗАНСЬКОГО РАЙОНУ) 1.56 MB
  Актуальність даного питання посилюється ще й тим, що в сучасних умовах здійснюється адаптація існуючої системи обліку та організації праці відповідно до міжнародних стандартів, впроваджуються нові методики організації обліку оплати праці на підприємствах.
80422. Развитие интеллектуальных умений при обучении математике (на примере умений анализировать, синтезировать, алгоритмизировать) 526 KB
  Чтобы учащиеся могли глубже осознать междисциплинарные связи, понять возможность переноса результатов с одного учебного предмета на другой, у них не должно создаваться впечатления, будто каждый предмет призван решать свои, отдельные от других дисциплин, задачи.
80423. Разработка алгоритма изготовления детали «Втулка-регулирующая» 862 KB
  Простейшие токарные станки были известны еще в глубокой древности. Эти станки были весьма примитивны по конструкции: заготовка вращалась от ножного привода, а режущий инструмент приходилось держать в руках. Работа на таких станках была непроизводительной, утомительной и неточной.
80424. Проектирование высокоскоростной корпоративной сети на базе технологии СЦИ 2.27 MB
  Данная дипломная работа заключается в разработке схемы проектирования и технической реализации корпоративной сети связи, на основе технологии СЦИ, с целью создания каналов связи высокого качества между 11-ми объектами, расположенными на территории Волгоградской области.
80425. Разработка финансовой модели проекта птичника на ЗАО «Агрофирма Боровская» 859 KB
  Необходимость существенного повышения уровня и качества жизни населения выдвигает в качестве неотложной задачи ускорение формирования нового агропромышленного производства на основе модернизации и ускоренного развития инновационных процессов, совокупности последовательно осуществляемых...
80426. СОЗДАНИЕ МОБИЛЬНОГО ИНФОРМАЦИОННОГО РЕСУРСА 143 KB
  В рамках данной дипломной работы будет описан процесс создания мобильной версии информационного ресурса Яковлевской центральной детской библиотеки в городе Строитель ориентированной в частности на учащихся средних школ Яковлевского района Белгородской области.
80427. Принцип разделения властей и его реализация к Конституции Российской федерации 1993-го года 127 KB
  Суть данного принципа заключается в том, чтобы не допустить узурпации власти в руках главы одной ветви власти, чтобы размеренно, путём системы сдержек и противовесов, одна ветвь власти влияла на другую, контролировала и выявляла недостатки в управлении, взаимодействовала, чтобы один орган не оказался таком положении...