Реализация двоичного поиска
Для определенности будем считать, что поиск происходит в массиве целых чисел (integer). Имя массива a и его элементы расположены в порядке неубывания (то есть каждый следующий элемент больше либо равен предыдущему).
Пусть мы ищем число, равное x.
Введем следующее постоянное свойство (инвариант): пусть left - это граница тех элементов, которые строго меньще x, пусть right - граница тех элементов, которые больше либо равны x.
На каждом шаге цикла будем поддерживать это свойство. Очевидно, что границы в какой-то момент встретятся (то есть будут указывать на соседние элементы).
function BinarySearch(x : integer; L, R : integer): integer;
var
left ,right, m: integer;
begin
left := L;
right := R;
while (right - left) > 1 do begin
m :=(right + left) div 2;
if a[m] < x then left := m
else right := m;
end;
BinarySearch := right;
end;
В результате работы цикла right содержит:
- Номер самого первого вхождения числа x в массив, если оно там есть;
- Номер самого первого числа, превышающего x, если его там нет.
Аналогичная реализация для языка C++
int bin_search(int x, L, R) {
int left, right, m;
left = L;
right = R;
while (right - left > 1) {
m = (right + left) / 2;
if (a[m] < x) left = m;
else right = m;
}
return right;
}
Последнее изменение: Суббота, 15 Август 2020, 02:34