Есть ли интуитивно понятное объяснение для прыжкового бинарного поиска? - PullRequest
Новая
       8

Есть ли интуитивно понятное объяснение для прыжкового бинарного поиска?

1 голос
/ 13 мая 2019

Я читаю Справочник программиста-конкурента: https://cses.fi/book/book.pdf

На страницах 32 и выше (PDF, стр. 42) упоминается метод 2 для двоичного поиска, в котором я не уверен, что японять полностью.Затем они слегка изменяют это, чтобы найти минимальное значение, такое, что функция ok () имеет значение true, и пытаются найти максимум в массиве.Я не понимаю, что здесь происходит.Есть ли какое-либо интуитивное объяснение? 

int k = 0;
for (int b = n/2; b >= 1; b /= 2) {
    while (k+b < n && array[k+b] <= x) k += b;
}
if (array[k] == x) {
    // x found at index k
}

Нахождение минимального значения, которое работает для функции ok 

int x = -1;
for (int b = z; b >= 1; b /= 2) {
    while (!ok(x+b)) x += b;
}
int k = x+1;

Найти максимальное значение для функции, которая сначала увеличивается, а затем уменьшается 

int x = -1;
for (int b = z; b >= 1; b /= 2) {
    while (f(x+b) < f(x+b+1)) x += b;
}
int k = x+1;

1 Ответ

1 голос
/ 13 мая 2019

Объяснения в книге очень хорошие!Я буду использовать их в качестве отправной точки.

Представьте, что у вас есть словарь, вы открываете его на первой странице (int k = 0;) и ищете слово в словаре (x).

Инвариантные допущения:

  1. слова в словаре расположены в неубывающем порядке (для каждого i, 0 <<code>i <<code>n: array[i-1] <= <code>array[i]),
  2. слово, которое вы ищете в данный момент на (array[k]) никогда не превосходит слово, которое вы ищете для (array[k] <= <code>x всегда верно).

b - это ваше предположение о том, на скольких страницах вы находитесь от ответа.В бинарном поиске вы всегда угадываете половину максимально возможного расстояния.Изначально самое большое возможное расстояние - это длина вашего словаря n.Итак, изначально вы берете половину длины словаря в качестве своей догадки - int b = n/2;.

Вы перемещаете свою текущую позицию на k вперед на предполагаемое количество страниц b так долго, как можете, т.е.до тех пор, пока предположение 2. выполняется.Затем вы снова догадаетесь, уменьшая вдвое ваше предполагаемое расстояние b.

Когда b становится 1, вы нашли страницу в словаре, который искали.Либо array[k] == x - словарь содержит слово на странице k, либо в вашем словаре такого слова нет.

Последние примеры с !ok(x+b) и f(x+b) < f(x+b+1) по существу совпадаюткак с array[k+b] <= x.

Представьте, что у вас есть массив со всеми возможными значениями !ok(i) в array[i] (или со всеми возможными значениями f(i) < f(i+1) в array[i]).Затем вы выполняете бинарный поиск по array так же, как с array[k+b] <= x.

Обратите внимание, что книга предполагает, что ok(i) и f(i) работают для любых i, в то время как размер массива ограничени нужно проверить: k+b < n, где n - размер массива.

Примечание по стилю кода в книге:

В конкурентном программировании, где у вас естьочень ограниченное количество времени для решения большого количества алгоритмических задач и больше никогда не смотреть на код, можно использовать короткие имена переменных, без комментариев и т. д. Также часто можно увидеть множество директив #DEFINE - см., например, https://gist.github.com/kodekracker/e09f9d23573f117a5db0.

Я понимаю, как это может быть очень удивительно.Чтение кода, способного читать код для скорости реализации, настолько недопустимо в мире долгосрочных профессиональных проектов.

...