title: What is the complexity of bisect algorithm?
body: <p>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?</p>
  
  <pre><code>#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 &lt; hi:
          mid = (lo+hi)//2
          midval = a[mid]
          if midval &lt; x:
              lo = mid+1
          elif midval &gt; x:
              hi = mid
          else:
              print True
              lo = hi
  </code></pre>
  
  <p>Reference:
  <a href="http://docs.python.org/library/bisect.html" rel="noreferrer">http://docs.python.org/library/bisect.html</a></p>