What is the complexity of bisect algorithm?

Question

I wrote code to understand which of them is faster when it comes to search an element in a list. It turns out to be bisect. What I do not understand is what is complexity of bisect algorithm and does it use Van Emde Boas tree?

#python inbuilt list search using 'in' took 0.0702499200317 secs

def mul3():
    a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]
    for x in a:
        if x in a:
            print x, "True"
        else:
            print x, "False"

#using bisect took 0.0649611193601

def mul4():
    a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]
    import bisect
    for x in a:
        locate = bisect.bisect_left(a, x)
        if locate == len(a) or a[locate] != x:
            print False
        print True

 #using binary search took 0.0651483638284


a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]


for x in a:
    lo = 0
    hi = 18
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x:
            hi = mid
        else:
            print True
            lo = hi

Reference: http://docs.python.org/library/bisect.html

Yb

Isn't a vEB tree only for integers? Bitsect works for all elements that can be compared. – Sulphurbottom

is there module in python providing implementation of vEB? – Yb

That's a different question, better ask it as such. May I ask why you need a vEB tree? dict is pretty much O(1), if you don't need order. And if requirements are harsh enough that binary search is out of question (O(log N) is already pretty great, even with billions of elements), wouldn't you want to not write it in Python to save a lot of space and time? – Sulphurbottom

I want to search a given number in a list which is most near to it. What would be the best approach? – Yb

Bisect would be pretty good for that (you only need to consider the items next to the returned index), and it's readily available. It also has a C implementation available, so it may easily beat anything you write in Python. – Sulphurbottom

For those algorithms that require a sorted list of values, your timing tests should include sorting them (instead of having them pre-sorted). Also the built-in list search will be affected by the order of the elements, so for it you'd need to randomize the order of the elements to get statistically meaningful results. – Knepper

Answer 1

It uses binary search, which makes it O(log n).

Puglia

Answer 2

There is binary search, right. O(Ln(n)) is the answer.

But, your list is not sufficient to test all the cases. All algorithms may took different execution times, but you have to test these with all the cases. If you test with enough many lists, you will get the right results.

I hope you're convinced.

Angeli