python(四)二分ルックアップ
1428 ワード
# coding:utf-8
import random
import time
def sort(alist, first, last):
if first >= last:
return
mid_value = alist[first]
low = first
high = last
while low < high:
while low < high and alist[high] >= mid_value:
high -= 1
alist[low] = alist[high]
while low 0:
mid = n//2
if alist[mid] == item:
return True
elif item < alist[mid]:
return binary_search(alist[:mid], item)
else:
return binary_search(alist[mid+1:], item)
return False
def binary_search_2(alist, item):
""" """
n = len(alist)
first = 0
last = n-1
while first <= last:
mid = (first + last)//2
if alist[mid] == item:
return True
elif item < alist[mid]:
last = mid - 1
else:
first = mid + 1
return False
if __name__ == "__main__":
seq = list(range(1, 10000))
li = random.sample(seq, 1000)
sort(li, 0, len(li) - 1)
print(li)
start = time.clock()
# print(binary_search(li, 104))
print(binary_search_2(li, 104))
end = time.clock()
print("time: %f " % (end - start))