Как я могу угадать (лучший алгоритм поиска) любое положительное целое число из системы, которая может ответить только да или нет?

Question

Допустим, система выдает «да» или «нет» только в том случае, если вы угадываете правильное число. Возьмем два примера, где

1. число = 3

2. number = 134567894567

Как видите, первый номер можно найти, если вы сделали линейный вызов, например: -

is the number = 1? No
is the number = 2? No
is the number = 3? Yes

Итак, алгоритм поиска linear было бы проще реализовать.

Однако, если размер элемента равен 134567894567 , возможно, будет иметь смысл использовать бинарный поиск . как мне построить систему, которая обеспечит наилучшие результаты с учетом вышеуказанных ограничений.

Answer 1

Вы не можете использовать двоичный поиск, если система даст вам ответ да / нет. Вам необходимо использовать линейный поиск.

Для использования двоичного поиска необходимы следующие условия:

1. Диапазон должен быть ограничен.
2. При каждом «угадывании» , он должен указать вам направление, в котором вам нужно двигаться.

Это минимальное требование для использования двоичного поиска. Поэтому для вашей текущей ситуации, когда вы не получаете требуемую информацию, вы должны использовать линейный поиск, как вы изначально предлагали.