Сводка
Частичная проверка того, что массив отсортирован так, что двоичный поиск применим, может быть выполнена в O (log n), как указано в OP, и в O (1).Метод O (log n) заключается в проверке каждого из датчиков относительно предыдущего, чтобы убедиться, что он сравнивается должным образом (меньше, больше, чем).Метод O (1) состоит в том, чтобы просто проверить последний элемент, найденный при бинарном поиске, и один рядом с ним, чтобы, если искомый элемент не был найден, было найдено хотя бы правильное место для вставки.Если искомый элемент был найден, то это хорошая O (1) частичная проверка.
Более подробное объяснение
Часть проблемы перед блоком кодаговорит, что распространенной проблемой является использование бинарного поиска в несортированном массиве.В основном, как можно использовать частичную проверку, чтобы проверить, отсортирован ли массив менее чем за O (n-1)?
Решение O (log n) состоит в том, чтобы проверить каждую из сеток бинарных поисковых зонков относительно предыдущего зонда (меньше или больше, чем ожидается).Это не гарантирует, что массив отсортирован, но это хорошая частичная проверка.
Единственная проверка O (1), о которой я могу подумать, - это проверить конечное место, в котором выполняется поиск, так, чтобы его значениеи соседние значения совпадают с идеей о том, где должен находиться искомый элемент, даже если элемент не был найден.Это довольно хорошая частичная проверка: если элемент найден, то, вероятно, все работает правильно.Если это не так, то проверьте элементы там, где это должно быть, чтобы они были на единицу меньше, чем искомый элемент, и затем на единицу больше, чем искомый элемент.Тем не менее, я понимаю, что проверка таким образом означает, что двоичный поиск, который является O (log n), уже был выполнен, поэтому я не знаю, действительно ли это O (1).Однако это только добавляет O (1) к общему поиску, поэтому я думаю, что это применимо.