Поиск элементов в массиве

Часть массива уже отсортирована. Подробнее обсудим проблему поиска заданного элемента x в отсортированном массиве a[1..n]. Простейший алгоритм линейного поиска можна организовать, используя цикл:

for i:=1 to n do

if a[i]=x

then kx:=I;

Одним из очевидных недостатков такого метода поиска является то, массив будет просматриваться от 1 до n, даже если элемент х уже найден. Эта проблема может быть легко решена например так:

B:=false; I:=1;

While not b do begin

if a[i]=x

then b:=true; Inc(i)

end; kx:=I-1;

Более серьезный подход состоит в использовании бинарного поиска (дихотомии). Обозначим крайние индексы слева L=1 и справа R=n. Тогда индекс среднего элемента M=(L+R) div 2. Если a[M]<x, то дальнейший поиск будем осуществлять только во второй половине массива, обозначив левый край как L=M, а иначе – в первой половине, обозначив R=M-1. Далее одну из выбранных половин массива снова разбиваем на две части и ищем, в какой из них расположен искомый элемент до тех пор пока a[M]=x. Представим описанный алгоритм в виде подпрограммы-функции:

function BinSearch(x:integer):size;

var i,L,R,M:size; b:Boolean;

begin

L:=1; R:=N; b:=false;

while (L<=R) and not b begin

M:=(L+R) div 2;

if a[m]=x

then b:=true

else if a[m]<x

then L:=M+1

else R:=M-1

end;

BinSearch:=M

end;

Этот алгоритм можно немного модернизировать, вводя фиктивный «барьер» a[0]=x:

L:=1; R:=N; a[0]:=x;

repeat

M:=(L+R) div 2;

if L>R

then M:=0

else if a[m]<x

then L:=M+1

else R:=M-1

until a[M]=0;

Используя стратегию бинарного поиска можно модернизировать процедуру сортировки массива вставкой, организовав более быстрый поиск нужной позиции в отсортированной части массива:

procеdure InsertSort (var a:vector; n:size);

var I,j,L,M,R:size; x:=integer;

begin

for i:=2 to n do begin

L:=1; R:=I-1; x:=a[I];

while (L<=R) begin

M:=(L+R) div 2;

if x > a[m]

then L:=M+1

else R:=M-1

end;

for j:=I-1 downto L do