Бинарный поиск на С++

Бинарный поиск может существенно ускорить процесс поиска данных. Стоит отметить, что работает он только для предварительно отсортированного массива.
Суть алгоритма: необходимо разбить массив на две половины в середине. Проверить середину на совпадение с искомыми данными, если совпадение найдено завершить поиск, если искомое значение больше/меньше серединного, продолжить поиск в той или иной части массива рекурсивно.

Приступим к построению класса, который использует данный алгоритм.

Из библиотек нам особо ничего не понадобится…

#include <iostream>
using namespace std;

Оприделим класс Search для поиска данных в массиве:

class Search{
private:
    int *X;
    int N;
public:
    Search(int size) { X = new int[N=size];}
    ~Search() {delete [ ]X; }
    void load_list(int input[ ]);
    void show_list(char *title);
    int binary_search(int S);
};

Теперь оприделим функции обозначенные в классе.
load_list — служит для загрузки массива в котором будет произведён поиск в наш класс. Тут всё просто, так что коментировать не буду…

void Search::load_list(int input[ ]){
    for (int i=0;i<N;i++)
        X[i] = input[i];
}

show_list — выводит на экран текстовую строку переданную в параметрах, а затем все члены массива поиска.

void Search::show_list(char *title){
    cout << "\n" << title;
    for (int i=0;i<N;i++)
        cout << " " << X[i];
    cout << "\n";
}

binary_search — занимается поиском данных переданный как параметр в определённом load_list массиве. Собственно именно в ней и находится всё ради чего делается остальное. Если совпадение найдено будет возвращён номер элемента, в противном случае — -1.

int Search::binary_search(int S){
    int head;
    int tail;
    int middle;
    int bmiddle;
    int amiddle;

    head = 0;  //голова (начало) массива
    tail = N;  //хвост (конец) массива

/* !!! предполагается, что массив был отсортирован по возврастанию  !!! */

    if ((S < X[0]) || S > X[N-1]) return(-1); //т.к. массив отсортирован можно сразу оценить данные которые в него не входят

    while(head<tail){
        middle = ((head + tail)/2) + 1;
        bmiddle = middle - 1;
        amiddle = middle + 1;
/* проверяем середину и соседние ей ячейки */

        if (S == X[middle] || S==X[bmiddle] || S== X[amiddle]) {
            if (S==X[middle]) return(middle);
            if (S==X[bmiddle]) return(bmiddle);
            if (S==X[amiddle]) return(amiddle);
        } else if (S>X[middle])
            head = middle + 1;
        else tail = middle - 1;
    }
    return(-1);
}

Ну и функция main для использования определённого класса:

int main(void) {
    int search_key;
    Search search_obj(10);
    static int sorted_list[] = {2,5,10,31,45,48,52,58,66,82};
    
    cout << "Бинарный поиск\n";
    search_obj.load_list(sorted_list);

    cout << "Что искать? "; cin >> search_key;
    
    search_obj.show_list("Ищем в:");

    int result = search_obj.binary_search(search_key);
    if (result != -1)
        cout << "Результат поиска: " << "X[" << result << "]=" << search_key;
    else cout << "Результат не найден.\n";

    return 0;
}

Вывод программы имеет такой вид:

Бинарный поиск
Что искать? 2
Ищем в: 2 5 10 31 45 48 52 58 66 82
Результат поиска: X[0]=2

Бинарный поиск выгоден тем, что он удачно использует информацию о том, что массив отсортирован. Он может спокойно выбросить (не исследовать) часть в которой точно нет необходимых данных.