title: Binary search in Erlang in lg(n) time
body: <p>I was searching through the possible work arounds for doing Binary search in Erlang and I found <a href="http://ruslanspivak.com/2007/08/15/my-erlang-binary-search/" rel="nofollow noreferrer">http://ruslanspivak.com/2007/08/15/my-erlang-binary-search/</a> But I was wondering if the solution in blog runs in O(lg n). Now since the recurrence for Binary search is:T(n) = T(n/2) + c  which gives me an execution time of O(lg n).</p>
  
  <p>Since in a C array you have the power of accessing any element in O(1) time. But in erlang if accessing the middle of list takes cn time, then binary search runs in linear overall time as poor as linear search. </p>
  
  <p>I came across lists:nth/2 BIF for finding the nth item in a list but I am not sure about its execution time.</p>
  
  <p>Any comments ?  </p>