Бинарный поиск в несортированном массиве

Question

Я сталкивался с этой проблемой: учитывая несортированный массив, найдите, сколько элементов можно найти с помощью бинарного поиска - например: [5,4,6,2,8] -> Ans: 3 -> '6' и '8'и' 5 'можно найти с помощью бинарного поиска

Я даже не могу понять, что значит делать бинарный поиск по несортированному массиву.Может кто-нибудь объяснить, пожалуйста, проблему?

Есть также код, который решает эту проблему:

private static int countPossibleMatches(int[] array, int left, int right, int min, int max) {
        if (right < left) {
            return 0;
        } else if (right == left) {
            return (array[left] >= min && array[left] <= max? 1 : 0);
        } else {
            int middle = (left + right) / 2;
            int count = (array[middle] >= min && array[middle] <= max ? 1 : 0);
            count += countPossibleMatches(array, left, middle - 1, min, Math.min(array[middle], max));
            count += countPossibleMatches(array, middle + 1, right, Math.max(array[middle], min), max);
            return count;
        }
    }

    static int countPossibleMatches(int[] array) {
        return countPossibleMatches(array, 0, array.length - 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

Answer 1

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

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

Следовательно

найдите, сколько элементов можно найти, используя бинарный поиск

просит вас ответить для данного массива, сколько его элементов можно найти с помощью алгоритма двоичного поиска.