Бинарный поиск

Question

Мне любопытно, если бы кто-нибудь мог объяснить мне реализацию бинарного поиска без ответвлений. Я видел это упомянутое в недавнем вопросе , но я не могу вообразить, как это будет реализовано. Я предполагаю, что было бы полезно избегать веток, если количество элементов достаточно велико.

Answer 1

Я предполагаю, что вы говорите о предложении «Создайте массив static const из всех идеальных квадратов в области, которую вы хотите поддерживать, и выполните быстрый бинарный поиск без ответвлений по нему».найденный в этот ответ .

Бинарный поиск "без ответвлений" - это просто развернутый цикл двоичного поиска.Это работает, только если вы заранее знаете количество элементов в массиве, который вы ищете (как если бы это было static const).Вы можете написать программу для написания развернутого кода, если он слишком длинный, чтобы делать это вручную.

Затем вы должны benchmark ваше решение, чтобы увидеть, действительно ли оно быстрее цикла.Если ваш код без ответвлений слишком большой, он не помещается в кэш быстрых команд ЦП и будет выполняться дольше, чем эквивалентный цикл.

Answer 2

Если у кого-то есть функция, которая возвращает +1, -1 или 0 в зависимости от позиции правильного элемента по сравнению с текущим, можно инициализировать позицию в размере списка / 2, а затем шаг в позиции / 2, а затемпосле каждого сравнения делайте положение + = направление * stepize;= размер шага размер шага / 2.Повторяйте, пока значение шага не станет равным нулю.