Целочисленный двоичный поиск — различия между версиями
Rukin (обсуждение | вклад) |
Rukin (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
== Алгоритм правостороннего/левостороннего поиска == | == Алгоритм правостороннего/левостороннего поиска == | ||
| − | [[Файл:cheme.jpg]] | + | [[Файл:cheme.jpg]]<br> |
Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым. | Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым. | ||
В случае равенства возвращать его, а если искомое больше(в случае правостороннего - не меньше), чем элемент сравнения, | В случае равенства возвращать его, а если искомое больше(в случае правостороннего - не меньше), чем элемент сравнения, | ||
| − | то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. | + | то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на 1, или же пока мы не найдём искомый индекс. |
| + | |||
| + | == Код == | ||
| + | l := 0; // l - левая граница | ||
| + | r := n + 1; // r - правая граница | ||
| + | while (l < r - 1) // запускаем цикл | ||
| + | begin | ||
| + | m := (l + r) div 2; // m - середина области поиска | ||
| + | if (a[m] < k) then l := m else r := m; // сужение границ | ||
| + | end; | ||
| + | if (a[r] = k) then result := r // выводим найденный индекс | ||
| + | else result := -1; // если элемент не найден возвращаем -1 | ||
| + | |||
| + | В случае правостороннего поиска изменится знак сравнения при сужении границ на (a[m] <= k), также при выводе найденного индекса, мы сравниваем искомый элемент k с a[l]. | ||
Версия 21:08, 24 мая 2012
Целочисленный двоичный поиск - алгоритм поиска аргумента для заданного значения монотонной целочисленной функции.
Содержание
Формулировка задачи
Пусть нам дана монотонная функция, значения которой целые числа. Нам необходимо найти место, где функция будет равна заданному значению.
Выбор границы
Нам должны быть заданы границы, на которых мы ищем индекс заданного значения х.
Правосторонний/левосторонний целочисленный двоичный поиск
Когда мы ищем правосторонним бин. поиском, то он возвращает индекс самого правого вхождения заданного значения х.
Когда же поиск левосторонний, возвращается индекс самого левого вхождения заданного значения х.
Это разделение помогает находить количество подряд идущих равных значений.
Например:
Задан отсортированный массив [1, 2, 2, 2, 2, 3, 5, 8, 9, 11]
Правосторонний поиск двойки выдаст в результате 5, в то время как левосторонний выдаст 2.
От сюда следует, что количество подряд идущих двоек равно длине отрезка [2;5] = 4.
Алгоритм правостороннего/левостороннего поиска
Файл:Cheme.jpg
Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым.
В случае равенства возвращать его, а если искомое больше(в случае правостороннего - не меньше), чем элемент сравнения,
то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на 1, или же пока мы не найдём искомый индекс.
Код
l := 0; // l - левая граница
r := n + 1; // r - правая граница
while (l < r - 1) // запускаем цикл
begin
m := (l + r) div 2; // m - середина области поиска
if (a[m] < k) then l := m else r := m; // сужение границ
end;
if (a[r] = k) then result := r // выводим найденный индекс
else result := -1; // если элемент не найден возвращаем -1
В случае правостороннего поиска изменится знак сравнения при сужении границ на (a[m] <= k), также при выводе найденного индекса, мы сравниваем искомый элемент k с a[l].
