'''
Created on Feb 27, 2011

@author: ola
'''

import random,time,bisect,sys

def get_number():
    return random.randint(0,sys.maxint)

def create_list(n):
    return [get_number() for i in xrange(0,n)]

def linear_search(search,nums):
    f = 0
    for i in search:
        if i in nums:
            f += 1
    return f

def binary_search(search,nums):
    f = 0
    nums.sort()
    for i in search:
        index = bisect.bisect_left(nums,i)
        if index == len(nums) or nums[index] == i:
            f += 1
    return f

def timings(size, search_size):
    nums = create_list(size)
    search = create_list(search_size/2)
    search.extend(nums[:search_size/2])
    funcs = [linear_search,binary_search]
    for f in funcs:
        start = time.time()
        found = f(search,nums)
        end = time.time()
        print "%s:size = %d\tsearch = %d\tfound=%d\ttime = %4.3f" % (f,len(nums), len(search),found,(end-start))

if __name__ == "__main__":
    timings(10000,5000)
    timings(10000,10000)
    timings(20000,10000)
    timings(20000,20000)