Разработка алгоритма за время Log N

Question

У меня проблемы с разработкой алгоритма, за время журнала N мой алгоритм будет подсчитывать все индексы, удовлетворяющие этому условию. 5,6,8,18,20], список A всегда сортируется.

ВСЕ ЦЕЛОЕ ЧИСЛО В СПИСКЕ УНИКАЛЬНО

Мне нужно найти все элементы, такие что | A [i] - i | <= c. Где C - целое число, переданное в качестве входных данных. </p>

То, что я пробовал до сих пор, - это алгоритм двоичного поиска, но я не совсем уверен, где разместить условные проверки

МОЙ КОД ЯВЛЯЕТСЯ БИНАРНЫМ ПОИСКОМ

low = 0
    high = len(arr) - 1


    while low <= high:

        mid = (high + low) // 2
        print(mid)
        if arr[mid] == x:
            return mid


        # Check if x is present at mid
        if arr[mid] < x:
            low = mid + 1

        # If x is greater, ignore left half
        else:
              high = mid - 1

        # If x is smaller, ignore right half


            # If we reach here, then the element was not present
    return -1

Answer 1

Дано:

Список A отсортирован, и все элементы уникальны, что означает, что Список A строго увеличивается .

Предполагая, что список A является нулевым индексом.

Наблюдение:

Предположим, что мы собираемся построить список B, для которого каждый элемент индекс i равен A [i] -i. Вы заметите, что список B всегда увеличивается (не строго).

Доказательство:

Для списка A

предположим, что элемент at (i) -й индекс будет x.

B [i] = xi

Тогда элемент с (i + 1) -м индексом будет больше x с минимумом (x + 1).

Итак, минимальное значение B [i + 1] = (x + 1) - (i + 1) = xi.

Итак, в худшем случае в списке B значение at (i +1) -й индекс будет равен значению в (i) -м индексе.

Пример:

Список A = [1,2,3,4, 5,6,8,18,20] # Строго возрастает

Список B = [1,1,1,1,1,1,2,11,12] # Увеличивается

Решение:

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

Это условие A [mid] - mid .

# Function performing binary Search
def binarySearch(c, A):
    low = 0
    high = len(A) - 1
    while low <= high:
        mid = low + (high-low+1)//2
        if A[mid]-mid > c:
            high = mid - 1
        else:
            low = mid + 1;
    return high;

A = [1,2,3,4,5,6,8,18,20]
num_Values = binarySearch(1, A)+1

# Number of values satisfying the condition (A[index] - index <=c)
print(num_Values)

# printing the values
for i in range(num_Values):
    print(A[i],end=" ")