Задача 1.
Дано целое х и массив целых чисел А[1], ..., А[n], которые отсортированы в порядке неубывания и уже находятся в памяти. Найти такое i, что A[i]=x, или возвратить i=0, если элемента x в массиве нет.
|
Решение задачи 1
Очевидное решение состоит в просмотре всего массива, что требует времени, пропорционального числу элементов массива. Однако этот алгоритм не использует того факта, что массив A уже отсортирован, и, вероятно, приведенное решение не является наилучшим.
Наилучший метод поиска состоит в том, чтобы проверить, является ли x средним элементом массива A. Если да, то ответ получен. Если x меньше среднего элемента, то мы можем применить тот же метод поиска к отсортированному подмассиву слева от среднего элемента; аналогично, если x больше среднего элемента, то в дальнейшем мы будем рассматривать правую половину массива.
Мы будем считать, что элемент A[0]=х; ответ возвращается в переменной mid, а через low и high обозначаются, соответственно, индексы начала и конца рассматриваемого подмассива. Цикл начинается при high-low=n-1 и завершается при high-low>=-1. На каждой итерации цикла величина high-low уменьшается по крайней мере вдвое по сравнению с ее предыдущим значением; таким образом, цикл будет проходиться не более [log2(n-1)]+2 раз (тут через [] обозначается целая часть числа, а log2 - это логарифм по основанию 2). Поэтому говорят, что сложность вышеизложенного метода (который обычно называется методом дихотомии - т.е. "деления на два") О(logn). Обратите внимание, что в выражение, стоящее в скобках после О не входит ничего кроме переменной n - мы рассматриваем только зависимость количества операций, которые необходимо выполнить, от длины имеющегося массива.
Function BSearch(var A:input_array; x,n:integer): integer;
var low,high,mid: integer;
begin
A[0]:=x;
low:=1;
high:=n;
repeat
mid:=(low+high) div 2;
if low>high
then mid:=0
else if A[mid]<x
then low:=mid+1
else high:=mid-1;
until (A[mid]=x);
BSearch:=mid;
end;
|
