Двоичный поиск

Очень часто программисту приходится работать с массивами. Также часто приходится определять содержит ли массив значение, соответствующее какому-либо заданному ключу. Этот процесс получил название поиска. Существует несколько разновидностей поиска: одни менее эффективны, но просты в использовании, другие более эффективны, но и, соответственно, более сложны, третьи более подходят для какого-либо вида массива или случая. В предыдущей статье рассматривался метод линейного поиска, который достаточно прост в использовании, но является неэффективным для больших и сортированных массивов. Для этих целей подходит метод двоичного поиска.

Перед применением алгоритма двоичного поиска массив обязательно должен быть отсортирован. В первом цикле делим весь наш исходный отсортированный массив пополам и сравниваем ключ поиска со средним значением (по которому делили массив). Если равны, то ключ поиска найден, иначе, если ключ поиска меньше этого среднего значения, то продолжим поиск в первой половине массива, в обратном случае, во второй части. В следующем цикле выбранную часть массива также делим пополам и, как и в предыдущем цикле выполняем сравнение. В случае, если ключ поиска не совпал с центральным элементом, выбираем нужную часть и в следующем цикле будем уже работать с ней. Т.е. после каждого сравнения отсекается ровно половина, сокращая тем самым область поиска. Так продолжается до тех пор, пока значение центрального элемента не совпадет с ключом поиска, либо не исчерпаются все элементы в получаемых подмассивах.

Для поиска в массиве, состоящем из 1024 элементов, потребуется максимум 10 сравнений, т.к. деление будет происходить так: 512, 256, 128, 64, 32, 16, 8, 4, 2, 1. Посчитать максимальное количество сравнений можно и таким образом: представим 1024 как 2 в 10-й степени. Число степени и будет нам говорить о количестве максимальных сравнений. К примеру, в массиве из 1 048 576 (2 в 20-й степени) элементов, нужно выполнить как максимум только 20 сравнений. Если брать в сравнение этот вид поиска и линейный поиск, то в массиве из 1 048 576 элементов, нужно было бы выполнить в среднем 1 048 576 / 2 сравнений, а это целых 524 288.

Для того, чтобы начинать программировать, нужно обязательно четко себе уяснить задачу, которую необходимо реализовать - также и в случае с алгоритмом двоичного поиска. Если вам не до конца понятен, после прочтения предыдущих абзацев, принцип его работы, то предлагаю сделать следующее: предложите напарнику загадать число в интервале, к примеру, от 1 до 1000, затем начинайте отгадывать его, называя центральные значения. Сначала назовите число 500, если не угадаете, то узнайте у напарника: является ли загаданное число большим, чем 500 или нет. Допустим, что загаданное число меньше, то называем центральное значение оставшегося подмассива чисел - 250. Далее следуем таким же образом, пока не угадаем. В самом наихудшем случае у нас будет как масимум 10 сравнений.

Теперь пришло время разработать программу, реализующую алгоритм двоичного поиска в массиве. Программа снабжена множеством комментариев, поэтому вам не составит труда разобраться с ее работой.

//Реализация алгоритма бинарного поиска в массиве

//подключаем необходимые заголовочные файлы
#include <iostream>
#include <iomanip>

//определяем прототипы функций
int binarySearch(int[], int, int, int, int);
void printHeader(int);
void printRow(int[], int, int, int, int);

//подключаем пространства имен
using namespace std;

int main()
{

    //выделяем память под переменные
    const int arraysize = 15;
    int array[arraysize];
    int key, result;

    //заполняем массив отсортированными данными
    for (int i = 0; i < arraysize; i++)

        array[i] = 2 * i;

    //запрашиваем и сохраняем ключ поиска
    cout << "Enter a key of search (0 - 28): ";
    cin >> key;

    //вызываем функцию, печатающую индексы массива
    //в качестве аргумента функция принимает размер массива
    printHeader (arraysize);

    //вызываем функцию, выполняющую бинарный поиск.
    //если функция найдет ключ поиска, то она вернет его индекс,
    //в обратном случае вернет -1
    result = binarySearch (array, key, 0, arraysize, arraysize);

    if (result != -1)

        cout << endl << key << " found in element of massiv " << result << endl;

    else

        cout << endl << key << " no found" << endl;

    return 0;

}

/*Данная функция самая важная - она то и выполняет бинарный поиск.
В качестве аргуметов она принимает, соответственно, массив, ключ поиска,
нижнюю границу массива, верхнюю границу массива, размер массива.
Первоначально нижней границей массива является 0, а верхней - размер массива,
т.к. в первой итерации бинарного поиска мы будем работать со всем массивом,
а уже во второй с половиной, третьей - половиной половины (четвертиной) и т.д.
*/
int binarySearch (int a[], int key, int low, int high, int size)
{

    //выделяем место в памяти для переменной, которая будет
    //у нас сохранять значение середины массива
    int middle;

    //цикл двоичного поиска
    //цикл длится, пока между границами массива есть значения
    while (low <= high)
    {

        middle = (low + high) / 2;

        //вызываем функцию вывода подмассива на экран
        printRow (a, low, middle, high, size);

        //если найден ключ поиска, то возвращаем его индекс
        if (key == a[middle])

            return middle;

        //в случае, если не найден ключ поиска, и его значение меньше
        //среднего значения, меняем верхнюю границу массива, тем самым
        //отсекая половину с большими значениями, в которой точно искать нечего
        else if (key < a[middle])

            high = middle - 1;

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

            low = middle + 1;

    }

    //если ключ поиска не найден в массиве, то возвращаем -1
    return -1;

}

//данная функция выводит на экран индексы элементов массива,
//с помощью которых визуально удобнее воспринимать массив
void printHeader (int size)
{

    cout << endl << "Indexes: " << endl;

    for (int i = 0; i < size; i++)

        cout << setw(3) << i << ' ';

    cout << endl;

    for (int i = 0; i < size; i++)

        cout << "----";

    cout << endl;

}

//данная функция в каждой итерации двоичного поиска выводит
//подмассив, участвующий в поиске
void printRow (int b[], int low, int middle, int high, int size)
{

    for (int i = 0; i < size; i++)
    {

        //элементы, не участвующие в поиске, не выводятся
        if (i < low || i > high)

            cout << " ";

        //средний элемент помечается звездочкой "*"
        else if (i == middle)

            cout << setw(3) << b[i] << '*';

        //участвующие в поиске элементы выводятся
        else

            cout << setw(3) << b[i] << ' ';

    }

    //перевод курсора на следующую строку
    cout << endl;

}

Результат работы программы:

Как мы видим по результатам работы программы, в первой итерации определяется середина массива, значением является число 14. Происходит сравнение ключа поиска с этим значением и, в случае несоответствия, продолжается поиск. Целью поиска выбирается подмассив меньших значений, т.к. в качестве ключа поиска мы ввели число 4, а оно в свою очередь меньше 14. Во второй итерации мы видим этот подмассив. Теперь серединой выбрано значение 6 - оно также не совпадает с ключом поиска, которое меньше 6 и, значит в разделенном пополам массиве также выбирается подмассив с меньшими значениями. Его мы видим с третьей итерации. На данном этапе наш подмассив уже состоит всего-лишь из трех значений, серединой выбирается 2. Сравниваем с ключом - не совпадает, 4 больше, чем 2, а значит поиск на следующей итерации будет проходить в подмассиве с большими значениями. На четвертой итерации мы видим, что наш подмассив состоит из всего-лишь одного числа, которое выбирается серединой, выполняется проверка и находится ключ. Выводим сообщение, что ключ поиска найден в элементе массива с индексом 2.

В данном примере было использовано максимальное число сравнений, равное четырем. Как вы уже знаете, максимальным числом возможных сравнений является степень числа 2, возведя в которую мы получим размер массива.