помогите написать алгоритм бинарного поиска со сложностью O(log2n)

Question

Условия следующие: Есть массив со значениями: например [14, 16, 19, 32, 32, 32, 56, 69, 72].- размеры книг....

Нужно написать функцию, которая бы принимала этот массив, размер новой книги и возвращала бы количество больших по размеру книг по алгоритму бинарного поиска. НО Вызывать готовые реализации бинарного поиска запрещено.

Например если вызвать функция со значением 32, то должно вернуть 3, если со значением 60 то 2!(т.к. только две книги на полке строго больше чем 60 страницы). и.т.д.
При этом продолжать поиск нужно именно бинарным поиском, нельзя просто взять и пройтись вправо по равным элементам до тех пор пока не встретим больший.... написал код

public class Main {
     public static int binarySearch(int[]arr, int x){
         int left = 0;
         int right = arr.length-1;
         while(left <= right) {
             int middleIndex = (left + right) / 2;
             // если средний элемент - целевой элемент, вернуть его индекс
             if (arr[middleIndex] == x) {

                 return (arr.length-1) - middleIndex;
             }

             // если средний элемент меньше
             // направляем наш индекс в middle+1, убирая первую часть из рассмотрения
             else if (arr[middleIndex] < x)
                 left = middleIndex + 1;

                 // если средний элемент больше
                 // направляем наш индекс в middle-1, убирая вторую часть из рассмотрения
             else if (arr[middleIndex] > x)
                 right = middleIndex - 1;

         }
         return -1;
     }
    public static void main(String[] args) {
    // write your code here
        int[]array = new int[]{12,13,14,15};
     int result =  Main.binarySearch(array,14);
        System.out.println(result);

    }

А если в массиве int[]array = new int[]{12,13,14,14,14,15}; вот так например?

Вот моё решение:

    public static int binarySearch(int[] arr, int x) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int middleIndex = (left + right) / 2;
        // если средний элемент - целевой элемент, вернуть его индекс
        if (arr[middleIndex] <= x && arr[middleIndex] < arr[middleIndex + 1]) {
            return (arr.length - 1) - middleIndex;
        } else if (arr[middleIndex] <= x && arr[middleIndex] == arr[middleIndex + 1]) {
            left = middleIndex + 1;
        }

        // если средний элемент меньше
        // направляем наш индекс в middle+1, убирая первую часть из рассмотрения
        else if (arr[middleIndex] < x)
            left = middleIndex + 1;

            // если средний элемент больше
            // направляем наш индекс в middle-1, убирая вторую часть из рассмотрения
        else if (arr[middleIndex] > x)
            right = middleIndex - 1;
    }
    return -1;
}

Answer 1

Как я понял вам нужно при int[]array = new int[]{12,13,14,14,14,15}; и x = 14, функция возвращала 1.

Тогда вам нужна функция, которая называется upper_bound, она возвращает индекс элемента, который строго > переданного в неё.

public static int upper_bound(int arr[], int x) { 
    int mid;
    int low = 0; 
    int high = arr.length; 

    while (low < high) {
        mid = low + (high - low) / 2; 

        if (x >= arr[mid]) 
            low = mid + 1;
        else 
            high = mid; 
    }
    return low; 
}

Теперь вы можете вызвать функцию upperd_bound передав в неё массив array и элемент x = 14. Если такого элемента не найдено, то будет возвращен размер переданного массива.

Далее от размера массива вы отнимаете результат функции и получаете кол-во книг.

Например в вашем примере будет возвращен индекс 5. Следовательно 6 - 5 = 1 - кол-во книг. Если x = 13, то будет возвращен индекс 2. Следовательно 6 - 2 = 4 - кол-во книг.

Сайт где рассказывается об этих функциях (только там на си код, но разница не большая)

БЛОГ НА HUSL

помогите написать алгоритм бинарного поиска со сложностью O(log2n)

Ответы (1 шт):