Задача 76258

Тема:    [ Многомерные массивы ]

Сложность: 2+ Классы:

Условие

(Двоичный поиск) Дана последовательность 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

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	2
Название	Массивы
задача
Номер	1.2.27