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

Пожалуй, первым приходит в голову следующий очевидный метод: сначала сравнить K со средним ключом в таблице. Результат сравнения позволит определить, в какой половине файла продолжить поиск, применяя к нему ту же процедуру, и т.д. После не более чем примерно log2 N сравнений либо ключ будет найден, либо будет установлено его отсутствие. Такая процедура иногда называется «логарифмическим поиском» или «методом деления пополам», но наиболее употребительный термин - бинарный поиск.

Недостатком бинарного поиска является необходимость последовательного сохранения списка, что осложняет выполнение операции добавления и удаления элемента.

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

Алгоритм B. ( Бинарный поиск). С помощью данного алгоритма разыскивается аргумент K в таблице значений R1,R2,...,Rn, ключи которых расположены в возрастающем порядке: K1<K2<...<Kn.

B1. [Начальная установка]. Установить l <=1, u<=1.

B2.[Нахождение середины]. (В этот момент мы знаем, что если K есть в таблице, то выполняются неравенства Kl £ K £ Ku.) Если u<l, то алгоритм заканчивается неудачно; в противном случае установить i £ (l-u)/2: теперь i указывает примерно в середину рассматриваемой таблицы.

B3.[Сравнение]. Если K<Ki, то перейти на B4; если K>Ki, то перейти на B5; если K=Ki, алгоритм заканчивается удачно.

B4. [Корректировка u]. Установить u<=i-1и вернуться к шагу B2.

B5.[Корректировка l]. Установить l<=i+1и вернуться к шагу B2.

Одна важная модификация. Соблазнительно вместо трёх указателей l, u, i использовать лишь два: текущее положение i и величину его изменения E; после каждого сравнения, не давшего равенство, мы могли бы установить i<=i+(-)E и E<=E/2(приблизительно). Этот путь реализуем, но он требует особой аккуратности в деталях, как в приведённом ниже алгоритме; более простые подходы обречены на неудачу!

Алгоритм U. ( Бинарный поиск). С помощью данного алгоритма разыскивается аргумент K в таблице значений R1,R2,...,Rn, ключи которых расположены в возрастающем порядке: K1<K2<...<Kn.

U1. [Начальная установка]. Установить i <=N/2, m<=N/2.

U2.[Сравнение]. Если K<Ki, то перейти на U3; если K>Ki, то перейти на U4; если K = Ki, алгоритм заканчивается удачно.

U3. [Уменьшение i]. (Мы определили положение интервала, где нужно продолжать поиск. Он содержит m или m-1 записей; i указывает на первый элемент справа от интервала.) Если m=0, то алгоритм оканчивается неудачно. В противном случае установить i<= i-(m/2); m<=m/2 и вернуться на U2.

U4. [Уменьшение i ]. ( Ситуация та же, что и в шагеU3, только i указывает на первый элемент слева от интервала.) Если m=0, то алгоритм оканчивается неудачно. В противном случае установить i<= i+(m/2); m<=m/2 и вернуться на U2.

 








Дата добавления: 2015-03-11; просмотров: 985;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.