Алгоритм бинарного поиска JAVA

Question

Алгоритм бинарного поиска JAVA

Рейтинг: -1Ответов: 2Опубликовано: 05.06.2023

Завел массив со значениями: [15 17 21 33 33 33 59 66 77]
Написал функцию, которая принимает массив, размер новой книги и возвращала бы количество больших по размеру.
Вызвал функцию, передав туда массив и размер новой книги, например 33. Должно было получиться 3, получается 4.
Потом проверил 66, тоже получил неверный результат 7.

Прошу помощи!

public class Main {
    public static void main(String[] args) {
        int[] arr = {15, 17, 21, 33, 33, 33, 59, 66, 77};
        int search = 33;
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int middle = (left + right) / 2;
            if (arr[middle] == search) {
                System.out.println(middle);
                break;
            } else if (arr[middle] > search) {
                right = middle - 1;
            } else if (arr[middle] < search) {
                left = middle + 1;
            }
        }
    }
}

java массивы алгоритм поиск

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

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

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

А для того, чтобы правильно обрабатывать дубликаты, код должен искать самое правое значение. Вот псевдокод из вики. Он так, как нужно, обрабатывает случаи дубликатов и отсутствия в списке

Even if T is not in the array, n-R is the number of elements in the array that are greater than T

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

На Java (онлайн пример)

int[] arr = {15, 17, 21, 33, 33, 33, 59, 66, 77};
int search = 33;

int L = 0;
int R = arr.length;

while (L < R) {
    int middle = (L + R) / 2;
    if (arr[middle] > search) {
        R = middle;
    } else  {
        L = middle + 1;
    }
}
System.out.println(arr.length - R);
//return arr.length - R;  если будете оформлять в виде функции

Answer 2

▲ 0

В дополнение ответа от MBo, следует проверить значения в крайних точках отсортированного массива, что позволит сократить сложность проверки в лучшем случае (если значение search выходит за диапазон чисел в массиве) до константной O(1).

Пример реализации:

public static int posFromRight(int search, int ... arr) {
    int left = 0;
    int right = arr.length;
    
    if (right > 0) {                             // массив не пустой?
        if (search < arr[left]) {                // проверить значение слева 
            right = 0;
        } else if (search >= arr[right - 1]) {   // проверить значение справа
            left = arr.length;
        }
    }
    
    while (left < right) {
        int mid = (left + right) / 2;
        if (arr[mid] > search) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return arr.length - right;
}

Тесты:

int[] arr = {15, 17, 21, 33, 33, 33, 59, 66, 77};
int[] tests = {10, 15, 16, 17, 30, 33, 60, 66, 70, 77, 80};

for (int t : tests) {
    System.out.printf("%d -> %d%n", t, posFromRight(t, arr));
}

Результаты:

10 -> 9
15 -> 8
16 -> 8
17 -> 7
30 -> 6
33 -> 3
60 -> 2
66 -> 1
70 -> 1
77 -> 0
80 -> 0

Предыдущее онлайн демо

Алгоритм бинарного поиска JAVA

Ответы