Лабораторная работа № 10. "ИССЛЕДОВАНИЕ МЕТОДОВ ЛИНЕЙНОГО И БИНАРНОГО ПОИСКА" кратко

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

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


Задача работы: овладеть навыками написания программ для методов линейного и бинарного поиска на языке программирования ПАСКАЛЬ .


Порядок работы :

• изучить описание лабораторной работы;

• по заданию, данному преподавателем, разработать алгоритм программы решения задачи;

• написать программу на языке ПАСКАЛЬ;

• отладить программу;

• решить задачу;

• оформить отчет.

Краткая теория

ПОИСК

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

a: ARRAY[0..N-1] OF item

Обычно тип item описывает запись с некоторым полем, выполняющим роль ключа. Задача заключается в поиске элемента, ключ которого равен заданному "аргументу поиска" x. Полученный в результате индекс i, удовлетворяющий условию a[i].key=x, обеспечивает доступ к другим полям обнаруженного элемента. Так как нас интересует в первую очередь сам процесс поиска, а не обнаруженные данные, то мы будем считать, что тип item включает только ключ, т.е. он есть ключ (key).

Алгоритм

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

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

1. Элемент найден, т.е. ai = x.

2. Весь массив просмотрен и совпадения не обнаружено.


Это дает нам линейный алгоритм:

i := 0;

WHILE (i < N) AND (a[i] <> x) DO

i := i+1 ;

END;

Обратите внимание, что порядок элементов в логическом выражении имеет существенное значение. Инвариант цикла, т.е. условие, выполняющееся перед каждым увеличением индекса i, выглядит так:

(0  i < N) AND (A_k : 0  k < i : a_k  x)

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

((i = N) OR (a_i = x)) AND (A_k : 0  k < i : a_k  x)

Это условие не только указывает на желаемый результат, но из него же следует, что если элемент найден, то он найден вместе с минимально возможным индексом, т.е. Об этом говорит сайт https://intellect.icu . это первый из таких элементов. Равенство i = N свидетельствует, что совпадения не существует.

Совершенно очевидно, что окончание цикла гарантировано, поскольку на каждом шаге значение i увеличивается, и, следовательно, оно, конечно же, достигнет за конечное число шагов предела N; фактически же, если совпадения не было, это произойдет после N шагов.

Ясно, что на каждом шаге требуется увеличивать индекс и вычислять логическое выражение. А можно ли эту работу упростить и таким образом убыстрить поиск ?

Единственная возможность - попытаться упростить само логическое выражение, ведь оно состоит из двух членов. Следовательно, единственный шанс на пути к более простому решению - сформулировать простое условие, эквивалентное нашему сложному. Это можно сделать, если мы гарантируем, что совпадение всегда произойдет. Для этого достаточно в конец массива поместить дополнительный элемент со значением x. Назовем такой вспомогательный элемент "барьером", ведь он охраняет нас от перехода за пределы массива. Теперь массив будет описан так:

a: ARRAY[0..N] OF INTEGER

и алгоритм линейного поиска с барьером выглядит следующим образом:

a[N] := x;

i := 0;

WHILE a[i] <> x DO

i := i+1;

END;

Результирующее условие, выведенное из того же инварианта, что и прежде:

(a_i=x) AND (A_k : 0  k < i : a_k  x)

Ясно, что равенство i = N свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.

Поиск делением пополам (двоичный поиск).

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

A_k : 1 k < N : a_k-1  a_k

Основная идея - выбрать случайно некоторый элемент, предположим am, и сравнить его с аргументом поиска x. Если он равен x, то поиск заканчивается, если он меньше x, то мы заключаем, что все элементы с индексами, меньшими или равными m, можно исключить из дальнейшего поиска; если же он больше x, то исключаются индексы больше и равные m. Это соображение приводит нас к следующему алгоритму (он называется "поиском делением пополам"). Здесь две индексные переменные L и R отмечают соответственно левый и правый конец секции массива а, где еще может быть обнаружен требуемый элемент.

L := 0;

R := N-1;

found := FALSE;

WHILE (L Ј R) AND NOT found DO

m := любое значение между L и R;

IF a[m] = x THEN found := TRUE;

IF a[m] < x THEN L := m+1

ELSE R := m-1;

END;

END;

Инвариант цикла, т.е. условие, выполняющееся перед каждым шагом, таков:

(L  R) AND (A_k : 0  k < L : a_k < x) AND (A_k : R < k < N : a_k > x)

из чего выводится результат

found OR ((L > R) AND (A_k : 0  k < L : a_k < x) AND (A_k : R < k < N : a_k > x))

откуда следует

(a_m = x) OR (A_k : 0  k < N : ak  x)

Выбор m совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача - исключить на каждом шагу из дальнейшего поиска, каким бы ни был результат сравнения, как можно больше элементов. Оптимальным решением будет выбор среднего элемента, так как при этом в любом случае будет исключаться половина массива. В результате максимальное число сравнений равно log N, округленному до ближайшего целого. Таким образом, приведенный алгоритм существенно выигрывает по сравнению с линейным поиском, ведь там ожидаемое число сравнений - N/2.

Эффективность можно несколько улучшить, поменяв местами заголовки условных операторов. Проверку на равенство можно выполнять во вторую очередь, так как она встречается лишь единожды и приводит к окончанию работы. Но более существенно следующее соображение: нельзя ли, как и при линейном поиске, отыскать такое решение, которое опять бы упростило условие окончания. И мы действительно находим такой быстрый алгоритм, как только отказываемся от наивного желания кончить поиск при фиксации совпадения. На первый взгляд это кажется странным, однако при внимательном рассмотрении обнаруживается, что выигрыш в эффективности на каждом шаге превосходит потери от сравнения с несколькими дополнительными элементами. Напомним, что число шагов в худшем случае - log N. Быстрый алгоритм основан на следующем инварианте:

(A_k : 0  k < L : a_k < x) AND (A_k : R  k < N : a_k  x)

причем поиск продолжается до тех пор, пока обе секции не "накроют" массив целиком.

L := 0;

R := N;

WHILE L < R DO

m := (L+R) DIV 2;

IF a[k] < x THEN L := m+1

ELSE R := m ;

END

END

Условие окончания - L і R, но достижимо ли оно? Для доказательства этого нам необходимо показать, что при всех обстоятельствах разность R-L на каждом шаге убывает. В начале каждого шага L < R. Для среднего арифметического m справедливо условие L Ј m < R. Следовательно, разность действительно убывает, ведь либо L увеличивается при присваивании ему значения m+1, либо R уменьшается при присваивании значения m. При L = R повторение цикла заканчивается. Однако наш инвариант и условие L = R еще не свидетельствуют о совпадении. Конечно, при R = N никаких совпадений нет. В других же случаях мы должны учитывать, что элемент а[R] в сравнениях никогда не участвует. Следовательно, необходима дополнительная проверка на равенство а[R] = x. В отличие от первого нашего решения приведенный алгоритм, как и в случае линейного поиска, находит совпадающий элемент с наименьшим индексом.

Задания

Варианты:

1.Найти наименьший элемент в массиве А с помощью линейного поиска.

2.Поиск элементов в массиве А, которые больше 30.

3.Вывести на экран все числа массива А кратные 3 (3,6,9,...) с помощью линейного поиска.

4.Найти все элементы, модуль которых больше 20 и меньше 50, с помощью линейного поиска.

5.Вывести на экран все числа массива А кратные 4 (4,8,...) с помощью линейного поиска.

6.Вывести на экран сообщение, каких чисел больше относительно 50, с помощью линейного поиска.

7.Найти элемент в массиве А и найти число сравнений с помощью линейного поиска.

8.Поиск элементов случайным образом с помощью бинарного поиска.

9.Дан список номеров машин (345, 368, 876, 945, 564, 387, 230), найти, на каком месте стоит машина с заданным номером, бинарный поиск .

10.Поиск каждого второго элемента в списке и число сравнений.

11.Найти элемент с заданным ключом с помощью бинарного поиска.

Вау!! 😲 Ты еще не читал? Это зря!

• бинарный поиск , метод деления пополам , поиск по бинарному дереву ,

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