Можно ли использовать бинарный поиск для находжения последнего вхождения элемента в массив?

#java #cpp #python #алгоритм #двоичный_поиск

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

Ответы

Ответ 1

Просто использовать разное поведение при решении, в какую сторону двигаться, если
нашли значение, равное искомому. Пример на Java:

int binarySearch(int[] a, int fromIndex, int toIndex, int key, boolean last) {
    int low = fromIndex;
    int high = toIndex - 1;

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

        if (midVal < key || (last && midVal == key))
            low = mid + 1;
        else if (midVal > key || (!last && midVal == key))
            high = mid - 1;
    }
    return last ? high : low;
}


Ответ 2

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


Ответ 3

Применяйте бинарный поиск, только ищите не само число, а число +- epsilon, где epsilon
- некое небольшой положительное число, гарантировано меньше разницы между двумя различными
числами. Если это массив целых чисел - epsilon может быть равен 0.5. Да, только нужно
понимать, что самого то числа в этом случае не найдем, но границу - да. Данный алгоритм
можно "немного ускорить", если верхнюю границу искать не от начала до конца, а от нижний
границы и до конца.


Ответ 4

Если с++, то алгоритм std::equal_range делает то, что требуется.


Ответ 5

В python это вообще реализуется двумя строками:

lower_bound = my_list.index(10)
upper_bound = len(my_list) - list(reversed(my_list)).index(10) - 1


Более оптимальный вариант:

lower_bound = my_list.index(10)
for k in range(lower_bound+1, len(my_list)+1):
    if my_list[k] != 10:
        break
upper_bound = k - 1


кол-во повторений: 10 000 000
список из 30 элементов  

первый вариант: 16.31380480196094  
второй вариант: 10.351039482047781