[Tutor] Binary search question

[Christian Witts]

Robert Berman 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'.
>
> Thanks for your input
>
> Robert Berman
>
> What you don't see with your eyes, don't invent with your mouth.
>
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> http://mail.python.org/mailman/listinfo/tutor
>
>   

Bisect and search.
If the list is sorted you easily know what the first and last element 
is.  Bisect the list, check that value, if it's higher than your target 
then bisect the bottom half of the list and check that and then it's a 
matter of rinse & repeat.

You'll be suprised how few bisections you will need to do in order to 
find your data.

-- 
Kind Regards,
Christian Witts