[Tutor] Binary search question

[Hugo Arts]

On Fri, Apr 23, 2010 at 4:05 PM, Robert Berman <bermanrl at cfl.rr.com> wrote:
> Hi,
>
> Given a list, list1 having 100,000 non repeating, sorted integers ,  which of
> the following methods is fastest to find an item fully understanding the item
> may or may not be in the list: The binary search method which is the standard
> search for such a small sample size, or the more python type statement is
> <value> in list1?
>
> What I am really trying to ascertain is how expensive or how efficient is  'is
> <value> in list1'.
>

Because the 'in' operator can't make any assumptions about the order
of the sequence (it has to work on unsorted data as well), it has to
check every item, which makes it O(n) time in the size of the
iterator.

A binary search requires data to be sorted, but works in O(log n), so
It will always be faster than a naive linear search like the in
operator performs.

HTH,
Hugo