Индекс выходит за пределы диапазона в bisect_left в Python 3 - PullRequest
Новая
       3

Индекс выходит за пределы диапазона в bisect_left в Python 3

0 голосов
/ 28 января 2020

Я пишу этот фрагмент кода, в котором я использовал функцию bisect_left из модуля bisect, который является сторонним модулем Python. Я использую его только с двумя параметрами, т.е. sorted_list и target (тот, для которого мне нужно найти подходящее значение индекса).

Проблема заключается в следующем: если моя цель больше, чем сумма наименьшего значения и Наивысшее значение, функция возвращает индекс = len (sorted_li), из-за которого я получаю ошибку индекса. Я могу использовать try и кроме, но более того, мне любопытно узнать, почему он так себя ведет.

Ниже приведен мой код: 

from bisect import bisect_left

li = [10,15,3,6,10]
k  = 19

def binary_search(sorted_list,target):

    index = bisect_left(sorted_list,target)

    print(index)

    if sorted_list[index] == target:
        return index

    else:
        return False

def function(sorted_li,k):

    """
    Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
    For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
    """

    print(sorted_li)

    for i in range(len(sorted_li)):

        print('Next iteration')

        print(sorted_li[i])

        target = k - sorted_li[i]

        j = binary_search(sorted_li,target)

        if j:
            if j != i:
                print(sorted_li[i])
                print(sorted_li[j])
                return True
            else:
                if j + 1 < len(sorted_li):
                    if sorted_li[j+1] == target:
                        print(sorted_li[i])
                        print(sorted_li[j+1])
                        return True
                if j - 1 > 0:
                    if sorted_li[j-1] == target:
                        print(sorted_li[i])
                        print(sorted_li[j-1])
                        return True
    return False


if __name__ == "__main__":

    li.sort()
    a = function(li,k)
    print(a)

Вывод выглядит следующим образом:

image sum (li's lowest + li's greatest)">

но когда я меняю k на 18, код работает нормально, вывод выглядит следующим образом:

When k <= sum (li's lowest + li's greatest)

Я пробовал разные наборы чисел для одного и того же. Выход остается прежним.

1 Ответ

1 голос
/ 28 января 2020

Вы используете bisect_left, который имеет следующую цель: он ищет точку вставки для x (которая является целью в вашем случае) в порядке, чтобы поддерживать отсортированный порядок.

Так что для вашего случая, когда вы Сначала вызовите двоичный двоичный поиск для 16 (19 - 3), он сравнит ваш номер с элементами в списке li, используя двоичный алгоритм, а затем вернет позицию для вставки 5, потому что в вашем списке [3, 6, 10 , 10, 15] точка вставки должна быть после 15. Это правильно.

Если вы откроете документацию , вы можете найти следующий метод в поиске отсортированного списка

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

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError
...