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

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

Ответ

Просто использовать разное поведение при решении, в какую сторону двигаться, если нашли значение, равное искомому. Пример на 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; }