On Fri, Apr 23, 2010 at 4:05 PM, Robert Berman <berma...@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 _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
