Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Поиск элементов в упорядоченном массиве






 

Задача поиска значения Х в упорядоченном по возрастанию значений массиве A(1)< A(2)<,.., < A(n) формулируется следующим образом. Требуется выяснить входит ли значение Х в этот упорядоченный массив, и если входит, то определить значение k, для которого А(k)=Х. Для такого типа задач применяется эффективный метод бинарного поиска, который также известен, как метод деления пополам. Сущность этого метода поиска заключается в последовательном определении номера S элемента, расположенного в точке деления упорядоченного массива пополам и сравнении искомого значения Х с этим элементом массива A(s). Если A(s)=Х, то поиск заканчивается. В противном случае возможны две ситуации: если A(s)< Х, то все элементы, имеющие номера с 1 по s также меньше Х, если A(s)> Х, то все элементы, имеющие номера с S по n также больше Х в силу упорядоченности массива по возрастанию значений. Поэтому для дальнейшего поиска половину значений массива можно исключить из рассмотрения. В первом случае - левую, во втором случае - правую половину. Рассмотрим пример. Допустим, что требуется определить совпадает ли значение Х=12 с каким-либо элементом в упорядоченном массиве А и если совпадает, то определить порядковый номер S этого элемента. Иллюстрация применения метода бинарного поиска для поиска элемента Х=12 в массиве (2, 3, 4, 6, 10, 12, 20, 30, 35, 45) приведена на рис. 30.

Элементы массива А (2, 3, 4, 6, 10, 12, 20, 30, 35, 45).

Номера элементов 1 2 3 4 5 6 7 8 9 10.

Первое деление S=5, А(5)=10 А(5)< Х), исключаем левую половину.

 

Элементы массива А (2, 3, 4, 6, 10, 12, 20, 30, 35, 45).

Номера элементов 1 2 3 4 5 6 7 8 9 10.

Второе деление S=8, А(8)=30 А(8)> Х), исключаем правую половину.

 

Элементы массива А (2, 3, 4, 6, 10, 12, 20, 30, 35, 45).

Номера элементов 1 2 3 4 5 6 7 8 9 10.

Третье деление S=6, А(6)=12 А(6)=Х), элемент Х=12 найден.

 

Рис.30. Иллюстрация применения метода бинарного поиска

 

 
 

На рис.31 представлен алгоритм, реализующий метод бинарного поиска в упорядоченном массиве.

 

Рис.31.Алгоритм поиска методом бинарного поиска






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.