Метод линейного поиска хорошо работает для небольших или для несортированных массивов. Однако, для больших массивов линейный поиск неэффективен. Если массив отсортирован, можно использовать высокоэффективный метод двоичного поиска.

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

В наихудшем случае двоичный поиск в массиве из 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 будет превышено число элементов в массиве.

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

const int arraySize = 15;

int a[arraySize], key, result;

for (int i = 0; i < arraySize; i++) размещение

данных в массиве

a[i] = 2 * i;

cout << Введите ключ - число, находящееся между О и 28: ; cin >> key;

printHeader(arraySize);

result = binarySearch(a, key, 0, arraySize - 1, arraySize); if (result != -1)

cout << endl key << найден в элементе массива result endl;

else

cout << endl << key << не найден << endl; return 0;

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

int binarySearch (int b[], int searchKey, int low, int high, int size)

int middle;

while (low <= high) {

middle = /low r high) / 2;

printRow(b, low, middle, high, size);

if (searchKey == b[middle]) соответствие

return middle; else if (searchKey < b[middle])

high = middle - 1; определение нижнего

конца массива

else

low = middle +1; определение верхнего

конца массива

return -1; searchKey не найден

Рис. 4.20. Двоичный поиск в сортированном массиве (часть 1 из 3)

Двоичный поиск в массиве I .iclude <iostream.h> iinclude <iomanip.h>

; binarySearch{int [], int, int, int, int); -d printHeader(int); lid printRow(int [], int, int, int, int);

cout << endl;

Печать одной строки, показывающей текущую обрабатываемую часть массива

void printRow(int b[], int low, int mid, int high, int size) {

for (int i = 0; i < size; i++) if (i < low I I i > high)

cout<< else if (i == mid)

cout << setw{3) << b[i] <<*; отметить

среднее значение

else

cout setw{3) b[i] cout endl;

Рис. 4.20. Двоичный поиск в сортированном массиве (часть 2 из 3)

4.9. Многомерные массивы

Массивы в С++ могут иметь много индексов. Обычным представлением многомерных массивов являются таблицы значений, содержащие информацию в строках и столбцах. Чтобы определить отдельный табличный элемент, нужно указать два индекса: первый (по соглашению) указывает номер строки, а второй (по соглашению) указывает номер столбца. Таблицы или массивы, которые требуют двух индексов для указания отдельного элемента, называются двумерными массивами. Заметим, что многомерный массив может иметь более двух индексов. Компиляторы С++ поддерживают по меньшей мере 12-мерные массивы.

Рис. 4.21 иллюстрирует двумерный массив а. Массив содержит три строки и четыре столбца, так что, как говорят, - это массив три на четыре. Вообще, массивы с m строками и п столбцами называют массивами m на п.

Каждый элемент в массиве а определяется именем элемента в форме а[ i ] [ j ]; а - это имя массива, а i и j - индексы, которые однозначно определяют каждый элемент в а. Заметим, что имена элементов первой строки имеют первый индекс 0; имена элементов в четвертом столбце имеют второй индекс 3.

Печать заголовка выходных данных void printHeader(int size) {

cout << endl << Индексы: << endl;

for (int i = 0; i < size; i++) cout setw(3) i ;

cout << endl;

for (i = 0; i < size; i++) cout ---- ;