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

StackOverflow https://stackoverflow.com/questions/2260272

  •  20-09-2019
  •  | 
  •  

Вопрос

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

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

Mid=(6+7)/2 т.е.6 в Яве

Это было полезно?

Решение

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

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);
}

Другие советы

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

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

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;
}

ПРИМЕЧАНИЕ

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

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

ПРИМЕЧАНИЕ

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

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

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

(6+7)/2.0 == 6.5

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

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

середина = (6+7)/2 + 1

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

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

или

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top