Bisection index search - why compare to len(a)?

So I'm trying to understand bisection. I get that it's a useful, computation-saving algorithm, I get the general concept of what it does and how it does it. What I don't get involves this search function that uses it, taken from https://docs.python.org/2/library/bisect.html

from bisect import bisect_left    

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

Could somebody please break down for me exactly what the i != len(a) part of the if line does? I can read it - it checks whether the insertion index of x is equivalent to the length of the list a - but I can't understand it. Why is it necessary? What would happen without it?

I follow that, let's say x has an insertion index greater than the length of a, then x obviously doesn't exist in a so it spews out the error - but if that's the case then the a[i] == x check trips it up anyway...?

Thanks!

Solution

Since lists are indexed from 0 then a[i] doesn't make sense for i == len(a) (the last element has index len(a) - 1). Doing a[i] for such i will throw an IndexError.

Now if bisect_left(a, x) returns len(a) then it means that the element should be added at the end of the list in order to preserve the order.

On the other hand if there is a match for x in a then

bisect_left(a, x) != len(a)

because If x is already present in a, the insertion point will be before (to the left of) any existing entries. If it is before then obviously the insertion index has to be smaller or equal to the last index (since in worst case this matched element will have last index) and the last index is len(a)-1 which is smaller then the length.

All in all if bisect_left(a, x) == len(a) then there is no x in a. This allows us to easily get rid of "IndexError problem" that I've mentioned at the begining.

Note that this (obviously) is not true for bisect_right. However following similar logic you can reach something analogous: if bisect_right(a, x) == 0 then there is no x in a. Unfortunately implementing index function via bisect_right would be more difficult since you would still need this check for i == len(a) to avoid an IndexError.