Я пытаюсь написать в Python функцию, которая находит первое число в отсортированном списке больше определенного значения, которое я передаю в качестве аргумента. В Интернете я нашел примеры, в которых используются простые списки, но для моих целей мне нужно часто выполнять эту операцию в больших списках, поэтому поиск, выполняемый за линейное время, слишком дорог.

Мне удалось написать итеративную бинарную поисковую функцию для достижения этой цели, хотя я сталкивался с некоторыми крайними случаями, когда она работает неправильно. Кстати, функция не обязана иметь дело со случаем, когда в списке нет более крупного элемента. Вот моя существующая функция:

def findFirstLarger(num, sortedList):
    low = 0; 
    high = len(sortedList) - 1

    mid = -1
    while True:
        print("low: " + str(low) + "\t high: " + str(high))
        if (low > high):
            print("Ah geez, low is " + str(low) + " and high is " + str(high))
            return # debugging, don't want this to happen
        if low == high:
            return sortedList[low]
        else:
            mid = (low + high) / 2;
            if num == sortedList[mid]:
                return sortedList[mid]
            elif num > sortedList[mid]:
                low = mid + 1
            else:
                high = mid - 1

Я заметил один случай, когда эта функция не работает:

>>> somenumbers=[n*2 for n in range(131072)]
>>> somenumbers[-5:]
[262134, 262136, 262138, 262140, 262142]


>>> binsearch.findFirstLarger(262139,somenumbers)
low: 0   high: 131071
low: 65536   high: 131071
low: 98304   high: 131071
low: 114688  high: 131071
low: 122880  high: 131071
low: 126976  high: 131071
low: 129024  high: 131071
low: 130048  high: 131071
low: 130560  high: 131071
low: 130816  high: 131071
low: 130944  high: 131071
low: 131008  high: 131071
low: 131040  high: 131071
low: 131056  high: 131071
low: 131064  high: 131071
low: 131068  high: 131071
low: 131070  high: 131071
low: 131070  high: 131069
Ah geez, low is 131070 and high is 131069

Здесь правильный результат будет262140, так как это первое число в списке больше262139.

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