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

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

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

В худшем случае двоичный поиск в массиве из 1024 элементов потребует только 10 сравнений. Повторяющееся деление 1024 на 2 (поскольку после каждого сравнения мы можем исключить половину элементов массива) дает 512, 256, 128, 64, 32, 16, 8, 4, 2 и 1. Число 1024 (2¹⁰) делится на 2 только десять раз. Деление на 2 эквивалентно одному сравнению в алгоритме двоичного поиска. Массив из 1048576 (2²⁰) элементов требует для нахождения ключа поиска самое большее 20 сравнений. Массив из одного миллиарда элементов требует для нахождения ключа поиска максимум 30 сравнений. Это огромное увеличение эффективности по сравнению с линейным поиском, который в среднем требует числа сравнений, равного половине числа элементов в массиве. Для миллиарда элементов выигрыш равен разнице между 500 миллионами сравнений и 30 сравнениями! Максимальное количество сравнений, необходимое для двоичного поиска в любом отсортированном массиве, может быть определено как первый показатель степени, при возведении в который числа 2 будет превышено число элементов в массиве.

Приведенная ниже Программа представляет итеративную версию функции BinarySearch, реализующей алгоритм двоичного поиска. Функция получает четыре аргумента - массив целых чисел b, целое число searchKey, индекс массива low и индекс массива high. Если ключ поиска не соответствует среднему элементу массива, то устанавливается такое значение индекса low или high, что дальнейший поиск проводится в меньшем подмассиве. Если ключ поиска меньше среднего элемента, индекс high устанавливается как middle - 1, и поиск продолжается среди элементов от low до middle - 1. Если ключ поиска больше среднего элемента, индекс low устанавливается как middle + 1, и поиск продолжается среди элементов от middle - 1 до high. Программа использует массив из 15 элементов. Степень двойки для первого числа, большего, чем количество элементов в данном массиве, равна 4 (16 = 2 ), так что для нахождения ключа поиска нужно максимум четыре сравнения. Функция PrintRow выводит каждый подмассив в процессе двоичного поиска. Средний элемент в каждом подмассиве отмечается символом звездочки (*), чтобы указать тот элемент, с которым сравнивается ключ поиска.

// Двоичный поиск в массиве
#include <iostream.h>

int BinarySearch(int [], int, int, int);
void PrintRow(int [], int, int);

const int arraySize = 15;

void main( void )
{
 int a[arraySize], key, result;

 // инициализация элементов массива
 for ( int i = 0; i < arraySize; i++) 
 a[i] = 2*i; 

 cout << "Input key, a number in [0,28]: ";
 cin >> key;

 // вызов функции BinarySearch и присвоение
 // возвращаемого ею значения переменной result
 result = BinarySearch(a, key, 0, arraySize - 1);
 if(result != -1)
 cout << '\n' << key << " found in " << result 
 << " element of array\n";
 else
 cout << '\n' << key << " not found \n";
}

// Двоичный поиск
int BinarySearch(int b[], int searchKey, int low, int high)
{
 int middle;
 while (low <= high)
 {
 middle = (low + high) / 2;

 PrintRow(b, low, middle, high);

 if (searchKey == b[middle])
 return middle;
 else if (searchKey < b[middle])
 high = middle - 1;
 else
 low = middle + 1;
 }
 return -1;
}

// печать одной строки, показывающей текущую 
// обрабатываемую часть массива
void PrintRow(int b[], int low, int mid, int high)
{
 for(int i = 0; i < arraySize; i++)
 if (i < low || i > high) 
 cout << " "; 
 else 
 {
 if (i * 2 < 10) 
 cout << " ";
 else 
 cout << " "; 
 
 if(i == mid)
 cout << b[i] << '*'; /* отметить среднее значение */
 else 
 cout << b[i] << ' ';
 }
 cout << '\n';
}

Фрагмент кода

 if (i * 2 < 10) 
 cout << " ";
 else 
 cout << " "; 

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

 #include<iomanip.h>

/*функция PrintRow с использованием манипуляторов потока*/
void PrintRow(int b[], int low, int mid, int high)
{
 for(int i = 0; i < arraySize; i++)
 if (i < low || i > high) 
 cout << " ";
 else if(i == mid)
 cout << setw(3) << b[i] << '*';
 else
 cout << setw(3) << b[i] << ' ';
 cout << endl;
}