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

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

Одним из подходов является сохранение инварианта на протяжении всего двоичного поиска.В вашем конкретном случае инвариант будет:

• array[low] < key
• key <= array[high]

Тогда вы можете минимизировать разрыв между низким и высокимиспользуя бинарный поиск.Когда low + 1 == high, high будет ответом.Пример кода на C ++:

// check invariant on initial values.
if (array[low] >= key) return low;
if (array[high] < key) return high+1;
// low + 1 < high ensures high is at least low + 2, thus
// mid will always be different from low or high. It will
// stop when low + 1 == high.
while (low + 1 < high) {
  int mid = low + (high - low) / 2;
  if (array[mid] < key) {
    low = mid;   // invariant: array[low] < key
  } else {
    high = mid;  // invariant: array[high] >= key
  }
}
return high;

Ключевое различие между этим и вашим примером кода заключается в обновлении low и high до mid вместо mid+1 или mid-1, потому что мы имеемпроверив значение array[mid], мы можем гарантировать, что инвариант все еще сохраняется при обновлении границ.Вам также нужно проверить инвариант начальных значений, прежде чем начинать поиск.

Answer 2

Для последнего появления элемента:

static int elementExists(int input[], int element){
    int lo=0;
    int high = input.length-1;
    while(lo<high){
        int mid = (lo + high )/2;
        if(element >input[mid] ){
            lo = mid+1;
        }
        else if(element < input[mid]){
            high= mid-1;
        }
        else if (high != input.length-1) //Change for the Occurrence check
            lo = mid;
        else {
            return mid;
        }
    }
    return -1;
}

Для первого вхождения:

else if (lo != mid){
        high = mid;
}

Answer 3

Это должно сработать

private static int bSearchVal(InvertedContainer.InvertedIndex[] a, int fromIndex,
                             int toIndex, long key) {
int low = fromIndex;
int high = toIndex - 1;
int result = low;
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
    {
        result = mid;
        high = mid -1; 
    }
}
return result; 

}

Answer 4

Вот вариант решения в Scala. Использовал сопоставление с образцом и рекурсию вместо цикла while, чтобы получить первое вхождение.

def binarySearch(arr:Array[Int],key:Int):Int = {
     def binSearchHelper(lo:Int,hi:Int,mid:Int):Int = {
        if(lo > hi) -1 else {
            if(arr(mid) == key) mid else if(arr(mid) > key){
                binSearchHelper(lo,mid-1,lo + (((mid-1) - lo)/2))
            }else{
                binSearchHelper(mid+1,hi,(mid+1) + ((hi - (mid+1))/2))
            }
        }
     }
    binSearchHelper(0,arr.size-1,(arr.size-1)/2)
}

def findFirstOccurrence(arr:Array[Int],key:Int):Int = {
    val startIdx = binarySearch(arr,key)
    startIdx match {
        case 0 => 0
        case -1 => -1
        case _ if startIdx > 0 => {
            if(arr(startIdx - 1) < key) startIdx else {
                    findFirstOccurrence(arr.slice(0,startIdx),key)
            }
        }
    }
}