Энциклопедия Turbo Pascal. Главы 1-4 - Двоичный поиск
ОГЛАВЛЕНИЕ
Двоичный поиск
Если данные отсортированы, то может использоваться очень хороший метод поиска, названный двоичным поиском. При таком поиске используется метод "разделяй и властвуй". Сначала производится проверка среднего элемента. Если его ключ больше ключа требуемого элемента, то делается проверка для среднего элемента из первой половины. В противном случае делается проверка среднего элемента из второй половины. Этот процесс повторяется до тех пор, пока не будет найден требуемый элемент или не будет больше элементов для проверки.
Например, для поиска числа 4 в массиве 1 2 3 4 5 6 7 8 9 указанным методом сначала делается проверка среднего элемента, которым является число 5. Поскольку этот элемент больше 4, поиск будет продолжен в первой половине массива, т.е. среди чисел
1 2 3 4 5. Здесь средним элементом является 3. Это значени.
меньше 4 и поэтому первая половина не будет больше рассматриваться и поиск продолжается среди чисел
4 5. На следующем шаге нужный элемент будет найден. При дво.
ичном поиске число сравнений в худшем случае равно
log n. Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице.
Приводимую ниже функцию, которая реализует двоичный поиск для символьных массивов, можно использовать для поиска любой произвольной структуры данных, изменив блок сравнения и определение типа данного "DataItem".
function BSearch (item: DataArray; count:integer;
key:DataItem):integer;
var
low, high, mid: integer;
found:boolean;
begin
low:=1; high:=count;
found:=false; { не найден }
while (low<=high) and (not found) do
begin
mid:=(low+high) div 2;
if key<item[mid] then high:=mid-1
else if key>item[mid] then low:=mid+1
else found:=true; { найден }
end;
if found then BSearch:=mid
else BSearch:=0; { не найден }
end; { конец поиска }
В следующей главе исследуются различные подходы к представлению данных, которые в некоторых случаях значительно облегчают сортировку и поиск.