Бинарный поиск (дихотомия)

Бинарный поиск в сортированной таблице – это разновидность метода деления интервала пополам для решения уравнения f(x)=0.

Действительно, если ключи интерпретировать как числа, то в сор­тиро­ванной таблице они следуют в неубывающем порядке, например, как это изображено на рис. 31.

Рис.31. Постановка задачи поиска в сортированной таблице

Приведенный ниже алгоритм отыскивает индекс заданного целого числа в массиве сортированных целых чисел.

int BinSearch(int Key, int n, int t[]){

// int t[] - массив длиной n, в котором производится поиск

// ключа Key

// в случае успеха функция возвращает индекс найденного

// элемента, а в случае неудачи - тот индекс, на котором

// находился бы ключ, если бы он был в таблице

int i,j,k;

i=0;j=n-1;

while(j>i+1){

k=(i+j)/2; // середина интервала

if(t[k]==Key) return k;

if(t[k]<Key){

i=k;

} else {

j=k;

}

}

if(t[i]<Key){

k=j;

} else {

k=i;

}

return k;

}

Очевидно, что число делений интервала пополам не превышает . Это и есть оценка быстродействия бинарного поиска. Функция bsearch, выполняющая бинарный поиск, входит состав библиотек, поставляемых практически с любым компилятором, и имеет прототип:

void *bsearch(const void *key, const void *base, size_t nelem, size_t width, int (*fcmp)(const void *a, const void *b ));

Аргументы:

- key – адрес записи, имеющей структуру такую же, как и запись таблицы. В этой записи заполнены только поля, составляющие ключ.

- base – адрес начала таблицы

- nelem – число записей в таблице

- width – длина записи в байтах

- fcmp – функция, определяемая пользователем, которая сравнивает ключи записей, имеющих адреса a и bи возвращает –1 (*a<*b), 0(*a==*b)и 1(*a>*b).

Функция bsearch возвращает адрес найденной записи или NULL.

Для поиска в сортированной таблице могут быть использованы любые методы решения уравнения Ключ=F(Адрес),в частности метод золотого сечения и интерполяционные методы.