Двоичный поиск является эффективным алгоритмом — его оценка сложности O(log2(n)), в то время как у обычного последовательного поиска O(n). Это значит, что например, для массива из 1024 элементов линейный поиск в худшем случае (когда искомого элемента нет в массиве) обработает все 1024 элемента, но бинарным поиском достаточно обработать log2(1024) = 10 элементов. Такой результат достигается за счет того, что после первого шага цикла область поиска сужается до 512 элементов, после второго – до 256 и т.д.
Недостатками такого алгоритма является требование упорядоченности данных, а также возможности доступа к любому элементу данных за постоянное (не зависящее от количества данных) время. Таким образом алгоритм не может работать на неупорядоченных массивах и любых структурах данных, построенных на базе связных списков.
Реализация
while (right – left > 1) // Пока правая граница правее левой
{
middle = (left + right) / 2; // Середина области поиска
if (A[middle] >= b)
right = middle; // Передвигаем правую границу
else
left = middle; // Иначе передвигаем левую границу
}
if (A[right] == X)
cout << right;
else
cout << -1;
где:
А - исходный массив,
N - размер массива,
X - искомое число,