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(Адрес),в частности метод золотого сечения и интерполяционные методы.