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

Question

Мой фрагмент кода:

int bs_greaterthan_or_equal(int *a, int key, int low, int high) {
    while(low<high) {
    int mid = low +(high-low)/2.0;
    if(a[mid]<key) {
    low = mid + 1;
    }
    else high = mid;
    }

    return high;
}

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

например, a [] = {1,3,10,15,20,25,27} key = 28 Возвращает 7

Answer 1

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

Потому что это то, для чего он был разработан.Технически говоря, он возвращает последний индекс + 1.

Обратите внимание на условие:

if(a[mid]<key) {
low = mid + 1;
}

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

При поиске ключа 28 в вашем примере, low постоянно обновляется, потому чтоВышеуказанное условие всегда оценивается как истинное.Когда mid равно 6, тогда a[mid] по-прежнему меньше, чем 28, поэтому low устанавливается на mid + 1, то есть 7. В этот момент low и high становятся равными (обратите внимание, что highникогда не изменялся) и цикл завершается.Функция возвращает 7.

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

int bs_greaterthan_or_equal(int *a, int key, int low, int high) {
    int max_limit = high;
    while(low<high) {
    int mid = low +(high-low)/2.0;
    if(a[mid]<key) {
    low = mid + 1;
    }
    else high = mid;
    }

    return high == max_limit ? -1 : high;
}

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