Эффективно найти индекс наименьшего числа, большего, чем какое-либо значение в большом отсортированном списке - PullRequest
Новая
       8

Эффективно найти индекс наименьшего числа, большего, чем какое-либо значение в большом отсортированном списке

0 голосов
/ 05 декабря 2018

Если у меня длинный список отсортированных чисел, и я хочу найти индекс наименьшего элемента, который больше некоторого значения, есть ли способ реализовать его более эффективно, чем использование бинарного поиска по всему списку?

Например: 

import random
c = 0
x = [0 for x in range(50000)]

for n in range(50000):
    c += random.randint(1,100)
    x[n] = c

Какой самый эффективный способ найти местоположение наибольшего элемента в х, меньшего некоторого числа, z

Я знаю, что выуже может сделать: 

import bisect
idx = bisect.bisect(x, z)

Но если предположить, что это будет выполняться много раз, будет ли еще более эффективный способ, чем бинарный поиск?Поскольку диапазон списка велик, для создания из всех возможных целых чисел требуется слишком много памяти.Можно ли было бы создать меньший список, скажем, каждые 5000 номеров и использовать его для ускорения поиска в определенной части большого списка?

1 Ответ

0 голосов
/ 05 декабря 2018

Можете ли вы попробовать, если это может быть решением?Генерация списка занимает много времени, но, кажется, быстро сообщает о результате.

Учитывая список: 

import random
limit = 50 # to set the number of elements
c = 0
x = [0 for x in range(limit)]

for n in range(limit):
    c += random.randint(1,100)
    x[n] = c
print(x)

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

z = 1600 # reference for lookup

res = ()
for i, n in enumerate(x):
  if n > z:
    res = (i, n)
    break

print (res) # this is the index and value of the elements that match the condition to break
print(x[res[0]-1]) # this is the element just before
...