Псевдокод для простого алгоритма поиска диапазона

Question

Я работаю над некоторыми практическими задачами для предстоящего экзамена CS.Я надеялся, что смогу получить некоторую помощь в определении псевдокода для этого алгоритма:

Учитывая массив n целых чисел, которые были отсортированы в возрастающем порядке, мне нужно дать описание псевдокода алгоритмавыполнить поиск диапазона А со сложностью O(r + logn), где r - количество выведенных точек.Другими словами, при заданном интервале [lo, hi] выведите все элементы массива A[i], где lo <= A[i] <= hi.

---

Я понимаю, что 'r' часть сложностибудет просто выводить элементы, которые находятся в пределах интервала (поместив их в отдельный массив в алгоритме).

Я не совсем уверен, как это сделать.Предполагается, что это всего лишь один алгоритм.Нужна ли рекурсия?Поскольку алгоритм должен быть log(n), деление массива постоянно кажется идеей.Я просто запутался в том, как это реализовать.

Answer 1

«Делить массив постоянно» правильно.Если вы делаете это путем деления пополам каждый раз, это называется «двоичным поиском», который действительно равен O (log (n)).

Вам придется выполнять поиск дважды, один раз для hi и один раз для lo, но это не меняет порядок сложности, поскольку мы умножаем на постоянное число итераций.

Answer 2

В качестве подсказки подумайте, как можно адаптировать алгоритм двоичного поиска , чтобы найти первый элемент, больший или равный lo, и последний элемент меньший или равный hi.Сколько времени займет каждый поиск?И как бы вы изменили бинарный поиск таким образом?