티스토리 뷰

Python

Binary Array Searching

techbard 2016.05.03 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


댓글
댓글쓰기 폼
공지사항
Total
407,537
Today
11
Yesterday
19
«   2019/09   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30          
글 보관함