Первое появление в бинарном поиске

Question

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

//ripped from the JDK
public static int binarySearchValue(InvertedContainer.InvertedIndex[] a, long key) {
    return bSearchVal(a, 0, a.length, key);
}

private static int bSearchVal(InvertedContainer.InvertedIndex[] a, int fromIndex,
                                 int toIndex, long key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long midVal = a[mid].val;

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return (low); // key not found. return insertion point
}

Answer 1

Дополнение к посту Джона Скитса:

Потенциальная потенциальная быстрая реализация на самом деле не сложна для реализации и добавляет только 2 строки кода, вот как я бы это сделал:

    if (midVal < key)
        low = mid + 1;
    else if (midVal > key)
        high = mid - 1;
    else if (low != mid) //Equal but range is not fully scanned
        high = mid; //Set upper bound to current number and rescan
    else //Equal and full range is scanned
        return mid;

Answer 2

Найдя a подходящее значение, вам в основном нужно пройтись по коллекции, пока не найдете запись, которая не соответствует.

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

Answer 3

Вы можете адаптировать свой существующий алгоритм поиска, просто имея более точное определение соответствия. Вы можете сказать, что выделенные 5 в последовательности 1,3, 5 , 5,5,9 являются первыми, потому что число перед ним (3) меньше 5. Поэтому, если середина попадает в массив элемент, равный ключу, который вы рассматриваете как совпадение, только если [mid-1] меньше ключа, другие равные элементы массива обрабатываются как больше, чем элементы. Теперь ваш алгоритм становится (после включения предложения Джона Скита вернуть отрицательные значения для точек вставки):

public static int binarySearch(int[] a, int key) {
    int low=0,high=a.length-1;
    while (low<=high) {
        int mid=(low+high) >>> 1;
        int midVal=a[mid];
        if (midVal < key) 
            low=mid+1;
        else if (mid>0 && a[mid-1]>=key) //we already know midval>=key here
            high=mid-1;
        else if (midVal==key) //found the 1st key 
             return mid;
        else
            return ~mid;      //found insertion point
    }
    return ~(a.length);       //insertion point after everything
}

Он использует больше сравнений, но в моих тестах работал быстрее, чем версия Stev314, вероятно, из-за эффектов кэша.

Answer 4

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

float array[];    //contains all integral values
int searchValue;

int firstIndex = -(binarySearch(array, (float)searchValue - 0.5F) + 1);

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

Также выполняется: log (n) time.

Пример:

import java.util.Arrays;

public class BinarySearch {
    // considering array elements are integers
    float ar[] = new float[] { 1, 2, 3, 3, 4, 4, 5, 9, 9, 12, 12 };

    public void returnFirstOccurrence(int key) {
        int firstIndex = -(Arrays.binarySearch(ar, key - 0.5F) + 1);
        if (ar[firstIndex] != key)
            System.out.println("Key doesn't exist");
        else
            System.out.println("First index of key is " + firstIndex);
    }

    public static void main(String Args[]) throws Exception {
        new BinarySearch().returnFirstOccurrence(9);
    }

}

ВЫВОД: 7

ps: я использовал этот трюк в нескольких конкурсах кодирования, и он всегда работал хорошо.

Answer 5

Вы можете реализовать алгоритм «нижней границы» вместо двоичного поиска. Этот алгоритм используется, например, в C ++ / STL и его расшифровка в Java проста. Алгоритмическая сложность нижней границы также O (log n) как бинарный поиск. Это лучше, чем использовать бинарный поиск первым и линейный поиск первого подходящего элемента - это будет иметь худшее поведение O (n).

Answer 6

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

Для вашего удобства я добавил соответствующие тесты Junit.

Answer 7

вот решение, которое я нашел для получения нижнего индекса ключа, имеющего несколько вхождений в отсортированном массиве, с помощью бинарного поиска.

int lowerBound(int[] array,int fromIndex, int toIndex, int key)
{
    int low = fromIndex-1, high = toIndex;
    while (low+1 != high)
    {
        int mid = (low+high)>>>1;
        if (array[mid]< key) low=mid;
        else high=mid;
    }
    int p = high;
    if ( p >= toIndex || array[p] != key )
        p=-1;//no key found
    return p;
}

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

 int upperBound(int[] array,int fromIndex, int toIndex, int key)
{
    int low = fromIndex-1, high = toIndex;
    while (low+1 != high)
    {
        int mid = (low+high)>>>1;
        if (array[mid]> key) high=mid;
        else low=mid;
    }
    int p = low;
    if ( p >= toIndex || array[p] != key )
        p=-1;//no key found
    return p;
}

Answer 8

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

while (upperbound > lowerbound)
{
  testpos = lowerbound + ((upperbound-lowerbound) / 2);

  if (item[testpos] >= goal)
  {
    //  new best-so-far
    upperbound = testpos;
  }
  else
  {
    lowerbound = testpos + 1;
  }
}

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

Это может быть адаптировано для других подобных поисков - например, поиск последнего ключа <= значение поиска. </p>

Это немного изменено по сравнению с моими предыдущими вопросами и ответами здесь .

Answer 9

Попробуйте это рекурсивное решение JavaScript. Это оптимально в том смысле, что это O (log (N))

function solve(A, e) {
  function solve (A, start, end, e, bestUntilNow) {
    if (start > end) {
      if (A[start] === e)
        return start
      return bestUntilNow
    } else {
      const mid = start + Math.floor((end - start) / 2)
      if (A[mid] === e) {
        return solve(A, start, mid - 1, e, mid)
      } else if (e < A[mid]) {
        return solve(A, start, mid - 1, e, bestUntilNow)
      } else {
        return solve(A, mid + 1, end, e, bestUntilNow)
      }
    }
  }
  return solve(A, 0, A.length, e, -1)
}

Answer 10

Я думаю, что более простой подход - сохранить последний индекс mid, где xs[mid] == key, в переменную результата, а затем продолжить бинарный поиск.

Вот быстрый код:

func first<T: Comparable>(xs: [T], key: T) -> Int {
    var lo = xs.startIndex
    var hi = xs.endIndex - 1
    var res = -1
    while lo <= hi {
        let mid = lo + (hi - lo) >> 1
        if xs[mid] == key { hi = mid - 1; res = mid }
        else if xs[mid] < key { lo = mid + 1}
        else if xs[mid] > key { hi = mid - 1 }
    }

    return res
}

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

func last<T: Comparable>(xs: [T], key: T) -> Int {
    var lo = xs.startIndex
    var hi = xs.endIndex - 1
    var res = -1
    while lo <= hi {
        let mid = lo + (hi - lo) >> 1
        if xs[mid] == key { lo = mid + 1;  res = mid }
        else if xs[mid] < key { lo = mid + 1}
        else if xs[mid] > key { hi = mid - 1 }
    }

    return res
}