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

Наиболее эффективным методом поиска в упорядоченном массиве без использования вспомогательных индексов или таблиц является бинарный поиск. Упрощенно этот метод состоит в том, что аргумент сравнивается с ключом среднего элемента таблицы. Если они равны, то поиск успешно закончился. В противном случае поиск должен быть осуществлен аналогичным образом в верхней или нижней половине таблицы [3].

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

low=l; hi=n; search = 0;

while (low<=hi)

{

mid=(low + hi)/2;

if (key= = k[mid])

{

search = mid;

cout<<”Элемент найден.Его номер=”<< mid;

return 0;

}

else

{

if ( key<k[mid]) hi =mid-1;

else low = mid+1;

}

}

Каждое сравнение в бинарном поиске уменьшает число возможных кандидатов сравнения в 2 раза. Таким образом, максимальное число сравнений ключа, которые будут сделаны, составляет приблизительно log₂n, т.е. алгоритм бинарного поиска имеет порядок O(log₂n).

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

Сбалансированные деревья (AVL-деревья)

Для удобства определим высоту пустого дерева как 0.

Баланс некоторого узла в дереве определяется как высота его левого поддерева минус высота его правого поддерева.

Сбалансированным бинарным деревом (деревом AVL) является такое бинарное дерево, у которого абсолютное значение баланса каждого узла £1.

Рис. 4.3. Сбалансированное бинарное дерево