Python
Binary Array Searching
techbard
2016. 5. 3. 14:51
반응형
# Binary Array Searching
from time import time
def contains(collection, target):
return target in collection
def bs_contains(ordered, target):
low = 0
high = len(ordered) - 1
while low <= high:
mid = (low + high) // 2
if target == ordered[mid]:
return True
elif target < ordered[mid]:
high = mid - 1
else:
low = mid + 1
return False
def performance():
n = 1024
while n < 50000000:
sorted = range(n)
now = time()
bs_contains(sorted, -1)
done = time()
print(n, (done - now) * 1000)
n *= 2
performance()
# 결과
1024 0.0
2048 0.0
4096 0.0
8192 0.0
16384 0.0
32768 0.0
65536 0.0
131072 0.0
262144 0.0
524288 0.0
1048576 0.0
2097152 0.0
4194304 0.0
8388608 0.0
16777216 0.0
33554432 0.0
반응형