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

Isn't a vEB tree only for integers? Bitsect works for all elements that can be compared. — , Aug 18 '12 at 21:08
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? — , Aug 18 '12 at 21:14
I want to search a given number in a list which is most near to it. What would be the best approach? — codersofthedark, Aug 18 '12 at 21:19
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. — , Aug 18 '12 at 21:21
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. — martineau, Aug 19 '12 at 01:29

score 27 · Accepted Answer · answered Aug 18 '12 at 21:08

27

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

answered Aug 18 '12 at 21:08

Ignacio Vazquez-Abrams

776,304
153
1,341
1,358

score 1 · Answer 2 · answered Aug 18 '12 at 22:09

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.

What is the complexity of bisect algorithm?

2 Answers2

Linked