Двоичный (или бинарный) поиск является эффективным алгоритмом поиска, выполняется он быстрее чем линейный поиск. Например, для массива из 1024 элементов линейный поиск в худшем случае (когда искомого элемента нет в массиве) обработает все 1024 элемента, но бинарным поиском достаточно обработать 10 элементов. Такой результат достигается за счет того, что после первого шага цикла область поиска сужается до 512 элементов, после второго – до 256 и т.д.
Недостатками такого алгоритма является требование упорядоченности данных, а также возможности доступа к любому элементу данных за постоянное (не зависящее от количества данных) время. Таким образом алгоритм не может работать на неупорядоченных массивах.
Алгоритм
1.Выбрать средний элемент A[c] и сравнить с X.
2.Если X = A[c], то нашли (стоп).
3.Если X < A[c], искать дальше в первой половине.
4.Если X > A[c], искать дальше во второй половине.
Реализация
где:
А - исходный массив,
N - размер массива,
X - искомое число,
Возможны и другие реализации
Например, с использованием досрочного выхода из цикла
