Разделите и покорите алгоритмы (применение бинарного поиска ?!)

Question

Я новичок здесь. Будучи студентом-градиентом, я некоторое время занимаюсь мозговым штурмом по алгоритмам. Я ценю любую помощь, которая может быть расширена в отношении проблемы ниже. Я искал достаточно, и я не мог найти никакого близкого решения этой проблемы.

У нас есть массив отсортированных различных чисел, который бесконечно длинный. Первые n чисел являются дробями, которые больше 0, но меньше 1. Все остальные элементы равны «1», и вам не присваивается значение n. Вам нужно разработать алгоритм, чтобы проверить, имеется ли в этом массиве заданная пользователем фракция F. Проанализируйте временную сложность алгоритма как функцию n. (Пример для n = 8, где 1 начинается с 8-го положения массива)

Мой подход: Я предполагаю, что лучший способ решить это - использовать двоичный поиск. Каждый раз, когда мы можем уменьшить размер массива наполовину и, наконец, придем к найденной части. Предположим, что в массиве есть m элементов, включая 1. Число дробных элементов равно n. Сложность выполнения бинарного поиска по всему массиву равна O (log (m)). Поскольку меня просят выразить временную сложность в терминах n, m = n + k (при условии, что число 1 в массиве равно k) Таким образом, временная сложность этой проблемы равна O (log (n + k)) ,

Пожалуйста, бросьте свои мысли. Спасибо

Answer 1

Вы действительно можете решить это для бесконечного массива, т. Е. Не зная m, экспоненциальным поиском.

Попробуйте первый элемент и удвоьте индекс, пока не получите 1. Это займет шаги O (Lg n). Затем вы переключаетесь на двоичный поиск и получаете ответ на дополнительные шаги O (Lg n).

Значение k не имеет значения.

Этот подход может иметь смысл в реальном мире, т. Е. С массивом конечного, но неизвестного размера, при условии, что по крайней мере половина массива заполнена единицами, так что поиск завершается в границах.