должно ли местоположение "средней точки" бинарного поиска всегда быть на 1/2?

Question

В собственном бинарном поиске мы выбираем 1/2 в качестве средней точки, чтобы отрезать половину «рабочей нагрузки» в линейном поиске и возможных ответов.Однако, если временная сложность функции check_mid (mid) не является фиксированной, будет ли 1/2 по-прежнему справедливой точкой для поиска?

Например, в задаче поиска первой неверной версии.скажем, временная сложность check_mid (mid) равна O (mid), длина массива равна N. Когда мы установим среднюю точку на 1/2, временная сложность линейного поиска в левой части будет 1/8 *N ^ 2, и правая часть будет 3/8 * N ^ 2.Таким образом, в аспекте «рабочая нагрузка» разделение несправедливо, будет ли фактор, который больше 1/2, будет лучшей средней точкой в ​​этой ситуации (1 / sqrt (2) или 2/3)?

Короче говоря, моя путаница заключается в том, что мы избавляемся от половины возможных случаев, или дела занимают половину «рабочей нагрузки»?Допустим, «рабочая нагрузка» -T означает линейную проверку всех возможных случаев.Если мы отрежем половину T в каждой рекурсии, худшая временная сложность будет log2 (T).Но если мы отрежем половину возможных случаев, худшая временная сложность не будет равна log2 (T), когда функция check_mid (mid) не зафиксирована.

Существует ли более эффективный фактор поиска, чемсредняя точка для бинарного поиска?

этот вопрос похож, но в его ответе не учитывалась временная сложность check_mid (mid).

Answer 1

Если вы заранее знаете что-то о распределении, возможно, вы могли бы найти лучшую точку поворота, в противном случае 1/2 думаю, что лучше всего что-то случайное [1,3,8,11,23..]. Никогда не знаете, в какой половине будет, а может быть, в особых случаях будет другая точка поворота.быстрее, но в целом время не самое лучшее. [для всех поисков].
В большинстве случаев бинарный поиск применяется к неизвестной последовательности.

Для известного распределения: exponential-grow [1 3 9 27 81 ...]очевидно, что очень-очень низкие значения будут близки к началу (или в 1/3), поэтому 1/3 может подойти для lower values и 2/3 для higher values.Но даже здесь, после нескольких итераций вряд ли можно предположить, в какой половине это «вероятно» будет (так что, возможно, если снова изменить точку поворота на 1/2, это даст лучшее время).Решение здесь основано на «хорошей возможности угадать правую половину (ту, у которой меньше элементов)» в течение нескольких итераций на основе известного распределения.