Binary Array Searching

Python

by 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