Задача 76258
|
|
 |
Условие
(Двоичный поиск) Дана последовательность
x[1]≤...≤x[n] целых чисел и число a.
Выяснить, содержится ли a в этой последовательности, то
есть существует ли i из 1..n, для которого
x[i] = a. (Количество действий порядка
log n.)
Решение
(Предполагаем, что n > 0.)
l := 1; r := n+1;
{r > l, если a есть вообще, то есть и среди x[l]..x[r-1]}
while r - l <> 1 do begin
| m := l + (r-l) div 2 ;
| {l < m < r }
| if x[m] <= a then begin
| | l := m;
| end else begin {x[m] > a}
| | r := m;
| end;
end;
(Обратите внимание, что и в случае
x[m] = a
инвариант не нарушается.)
Каждый раз
r - l уменьшается примерно вдвое, откуда
и вытекает требуемая оценка числа действий.
Замечание.
l + (r-l ) div 2 = (2l + (r - l)) div 2 = (r + l) div 2.
В этой задаче существенно, что массив упорядочен — поиск
в неупорядоченном массиве требует времени,
пропорционального длине массива. (Чтобы убедиться, что
какого-то числа нет в массиве, надо просмотреть все его
элементы.)
1000
