Двоичный поиск является эффективным алгоритмом — его оценка сложности O(log2(n)), в то время, как у обычного последовательного поиска O(n). Это значит, что, например, для массива из 1024 элементов, линейный поиск, в худшем случае, когда искомого элемента нет в массиве, обработает все 1024 элемента. Бинарным поиском достаточно обработать \(log_2(1024) = 10\) элементов. Такой результат достигается за счет того, что после первого шага цикла область поиска сужается до 512 элементов, после второго – до 256 и т.д.
O(log2(n))
O(n)
пока (right – left > 1) // Пока правая граница правее левой нц middle = (left + right) / 2; // Середина области поиска если (A[middle] >= b), то right = middle; // Передвигаем правую границу иначе left = middle; // Иначе передвигаем левую границу кц если (A[right] == X), то вывод right; иначе вывод -1;
А
N
X
K
NO
1000 ms 32 Mb Правила оформления программ и список ошибок при автоматической проверке задач