index of a first occurrence (inequality match) in a list

Question

A=[2,3,5,7,11,13]
print(A.index(5))

The answer is 2, But what I need is the first one which is bigger than 4 (the answer will be the same - 2). I can apply a while loop, but is there a more elegant or a builtin way to do it? In my problem the list is sorted in an ascending order (no duplication), and my target is to split it into two lists: lower or equal to 4, and bigger than 4; and given the list is sorted it would be redundant to scan it twice (or even once).

Answer 1

As @DanD.mentioned, you can use the bisect module for this, in you example you can use bisect_left

>>> import bisect
>>> bisect.bisect_left(A, 5)
2

This will use a binary search since your data is sorted, which will be faster than a linear search (O(logN) instead of O(N)).

If you want the index of the first value greater than 4, then you can switch to bisect_right

>>> bisect.bisect_right(A, 4)
2

Answer 2

You're totally correct about efficiency - if you have already sorted list, do not iterate linearly, its waste of time

There's built-in bisect module - exactly for binary search in sorted containers.

You're probably looking for bisect_right function.