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

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

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

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

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

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

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

// ключа Key

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

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

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