Index going out of range in bisect_left in Python 3

Question

I'm writing this piece of code, in which I've used bisect_left function from the bisect module which is a first-party module of Python. I'm using it with two parameters only i.e. sorted_list and target(the one for which I have to find the suitable index value).

The issue is: If my target is greater than the sum of lowest value and highest value, the function is returning the index = len(sorted_li), due to which I'm getting index error. I can use try and except but more than that I'm curious to know why it is behaving like so.

Following is my code:

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)

It's output is as follows:

but when I'm changing k to 18, the code is working fine, the output is as follows:

I've tried with various sets of numbers for the same. The output remains the same.

Answer 1

You're using bisect_left which has next purpose: it looking for the insertion point for x (which is target in your case) in a to maintain sorted order.

So for your case when you call first binary_search first time for 16 (19 - 3), it compare your number with items in li list using binary algorithm and then it returns position for insert 5, because in your list [3, 6, 10, 10, 15] insertion point should be after 15 which is correct.

If you open documentation you can find next method in searching sorted list

which does exactly you need, it searching for the exact item in list and return position of it if it exists either it raises ValueError because item not found.

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