[Tutor] A faster x in S

[Kent Johnson]

Dinesh B Vadhia wrote:
> For some significant data pre-processing we have to perform the 
> following simple process:
>  
> Is the integer x in a list of 13K sorted integers.  That's it except 
> this has to be done >100m times with different x's (multiple times).  
> Yep, a real pain! 
>  
> I've put the 13K integers in a list S and am using the is 'x in S' function.
>  
> I was wondering if there is anything faster?

Yes. Put the integers in a set and test for membership there. If for 
some reason the integers have to be in a list, and the list is sorted, 
use the bisect module to do a binary search, rather than the linear 
search used by 'x in S'.
http://docs.python.org/lib/module-bisect.html

Kent