Измените бинарный поиск, чтобы найти все целые числа в массиве больше, чем x и меньше, чем 2x, с временной сложностью лучше, чем O (n)

Question

Пусть A - отсортированный массив, содержащий n различных натуральных чисел.Пусть x - положительное целое число, такое, что x и 2x не входят в A.

Опишите эффективный алгоритм для поиска числа целых чисел в A, которые больше x и меньше 2x

какова сложность алгоритма?кто-то может написать псевдокод без использования библиотек?

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

def find_integers(A, x):
    integers = 0
    for element in A:
        if element > x and element < 2*x:
            integers += 1
    return integers 

Answer 1

У меня небольшая задача улучшить бинарный поиск по умолчанию для всех.Как я описал в этом ответе: Как я могу упростить этот рабочий код бинарного поиска в C? ...

... почти все мои бинарные поиски ищут позиции вместо элементов, поскольку это быстрее и проще в правильном понимании.

Он также легко адаптируется к таким ситуациям:

def countBetweenXand2X(A,x):
    if x<=0:
        return 0

    # find position of first element > x

    minpos = 0
    maxpos = len(A)
    while minpos < maxpos:
        testpos = minpos + (maxpos-minpos)//2
        if A[testpos] > x:
            maxpos = testpos
        else:
            minpos = testpos+1

    start = minpos;

    # find position of first element >= 2x

    maxpos = len(A)
    while minpos < maxpos:
        testpos = minpos + (maxpos-minpos)//2
        if A[testpos] >= x*2:
            maxpos = testpos
        else:
            minpos = testpos+1

    return minpos - start

Это всего лишь 2 бинарных поиска, поэтому сложность остается O (log N) .Также обратите внимание, что второй поиск начинается с позиции, найденной в первом поиске, поскольку мы знаем, что вторая позиция должна быть >= первой.Мы достигаем этого, просто оставив minpos в покое, вместо того, чтобы обнулять его.

Answer 2

Как вы уже узнали, вы можете использовать бинарный поиск.Ищите x и 2x и запишите позиции в списке, вы можете вычислить количество целых чисел из разницы между двумя позициями.

Поскольку вы используете python, модуль bisect можетпомочь вам с бинарным поиском.