Количество элементов, доступных для двоичного поиска в данном массиве

Учитывая массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы найти максимальное количество целых чисел, доступных для двоичного поиска в данном массиве.

Примеры:

Input: arr[] = {1, 3, 2}
Output: 2
Explanation: arr[0], arr[1] can be found.

Input: arr[] = {3, 2, 1, 10, 23, 22, 21}
Output: 3
Explanation: arr[1], arr[3], arr[5] can be found using binary search irrespective of whether the array is sorted or not.

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

• Создайте переменную count = 0 , которая будет хранить количество элементов, доступных для двоичного поиска.
• Для каждого элемента выполните бинарный поиск в диапазоне [0, N) как:
  • Инициализируйте переменную l как 0 и r как N-1 и выполните двоичный поиск для arr[i] .
  • Для каждой итерации цикла while, пока l не станет меньше r, вычислите среднее значение, обозначаемое как (l + r)/2 .
    • Если arr[mid] равно arr[i] , тогда счетчик увеличивается на 1 .
    • Если arr[mid] меньше, чем arr[i], то замените l на mid + 1 .
    • В противном случае измените r на mid – 1 .
• Окончательный ответ будет храниться в переменной count .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log (N))
Вспомогательное пространство: O(1)