Как найти последний элемент массива в бинарном поиске

Question

В алгоритме бинарного поиска верхний предел элемента равен array.length-1, тогда как мне найти последний элемент массива?

Если нижняя и верхняя границы для элемента массива длиной 8 равны 6 и 7 соответственно, то мой средний элемент получается как:

mid = (6 + 7) / 2, т.е. 6 в java

Answer 1

Это действительно сводится к использованию правильного сравнения с правильно выбранной средней точкой. Например (без объявлений типов переменных),

binsearch(a,val,left,right){
    if(left==right) return left;
    mid = (left+right)/2;
    if(a[mid] < val)
        return binsearch(a,val,mid+1,right);
    else
        return binsearch(a,val,left,mid);
}

даст вам индекс самого левого элемента, который соответствует значению val (даже если это самый правый элемент в массиве). Вам не нужно явно проверять последние два или округлять, а не использовать встроенное целочисленное усечение.

Однако, если вы хотите, чтобы индекс самого правого элемента равнялся val, вам нужно изменить оператор <на>, а mid должен быть задан как

mid = (left+right+1)/2;

Это так просто.

Редактировать: Еще одна вещь, я посмотрел на свой код, который я использую для этого, и понял, что вы должны также изменить вызовы binsearch, чтобы в конечном итоге оказаться на самом правом элементе. Я просто выложу полный код для этого (что я должен был сделать в первую очередь). Вот бинарный поиск, чтобы найти самый правый элемент, равный val.

binsearch(a,val,left,right){
    if(left==right) return left;
    mid = (left+right+1)/2;
    if(a[mid] > val)
        return binsearch(a,val,left,mid-1);
    else
        return binsearch(a,val,mid,right);
}

Answer 2

Самый простой подход - использовать полуоткрытые диапазоны. Таким образом, ваша верхняя граница указывает на один шаг после последнего действительного элемента в массиве, хотя ваша нижняя граница указывает непосредственно на первый элемент. Однако во время поиска вы рассматриваете свой диапазон как включающий - верхняя граница вне диапазона является действительным результатом "не найдено совпадений".

В начале каждой итерации у вас есть ...

lower <= target <= upper

«цель» означает индекс, который будет найден и возвращен.

Вы вычисляете середину как "(верхняя + нижняя) / 2". Так как это усекает, mid никогда не может быть таким же, как upper, что важно. Поскольку «верхний» может быть за пределами, мы никогда не сможем юридически оценить «массив [верхний]».

Чтобы найти первый элемент, больше или равный ключу ...

if array[mid] >= k :  lower <= target <= mid
if array[mid] <  k :  mid+1 <= target <= upper

Чтобы найти первый элемент больше, чем ключ ...

if array[mid] >  k :  lower <= target <= mid
if array[mid] <= k :  mid+1 <= target <= upper

Эти поддиапазоны являются инклюзивными и должны точно соответствовать, но не перекрываться. Единственное наложение элемента в середине (простая ошибка) приводит к бесконечным циклам, что является частью того, почему мы используем mid + 1 для одного поддиапазона.

Обратите внимание, что все, что изменяется между двумя поисками, это оператор сравнения.

Чтобы найти последнее меньше или равно, найдите первое больше и вычтите одно из результата. Вы можете получить -1, если все элементы в массиве больше, чем ключ.

Примечание - вы проверяете ключ только против середины на каждой итерации (вы знаете, что нижняя и верхняя границы уже верны) и вы делаете только один условный тест.

Выполните проверку вне границ и проверку равенства (если это то, что вам нужно) вне цикла.

int find_first_ge (int key)
{
  int lower = 0;
  int upper = array.length;

  while (upper > lower)
  {
    int mid = (lower + upper) / 2;

    if (array [mid] >= key)  //  for find_first_gt, use ">" here
    {
      upper = mid;
    }
    else
    {
      lower = mid + 1;
    }
  }

  return lower;
}

Примечание

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

Хитрость заключается в том, чтобы гарантировать, что разделенные пополам поддиапазоны будут точно такими, как необходимо после каждого ключевого теста, и всегда как минимум на единицу меньше, чем исходный полный диапазон - и из-за чрезмерной уверенности и плохой памяти, это именно то, что удалось ошибиться. Вышесказанное основано на реальном работающем коде в интенсивно используемой библиотеке (поиск в узле в многолинейной библиотеке), поэтому, если это не так, у меня big проблемы; -)

Примечание

Отредактировано снова, чтобы улучшить формулировку и упростить описания границ поддиапазонов (отмечая, что, хотя диапазоны полуоткрыты, они рассматриваются как включающие).

Answer 3

Двоичный поиск, как известно, сложно сделать абсолютно правильно. В Programming Pearls , книге, которую каждый программист, вероятно, должен был прочитать хотя бы один раз, должен быть очень тщательный анализ различных проблем и крайних случаев.

Answer 4

Когда ваша нижняя граница и верхняя граница находятся в пределах друг от друга, отметьте оба.

Answer 5

Вы можете округлять каждый раз.

(6 + 7) /2,0 == 6,5

Округлите, и вы получите 7.

Или вы можете просто добавить один к своей средней точке.

mid = (6 + 7) / 2 + 1

Другой способ - изменить начальную или конечную точку на +1 или -1 для следующей рекурсии. Это то, что статья в википедии на эту тему показывает в некоторых реализациях.

мин = середина + 1

или

макс = середина 1