#!/usr/bin/python
""" 折半查找算法
"""
#定義函數
def BinarySearch(a, X, N):
left, right = 0, N-1
while (left <= right):
middle = ( left + right ) / 2
if (X < a[middle]):
right = middle - 1
elif (X > a[middle]):
left = middle + 1
else:
return middle
return -1 #"not found"
#調用函數
arr = [10,20,30,40,50,60,70]
BinarySearch(arr, 40, len(arr))
3 回答
慕雪6442864
TA貢獻1812條經驗 獲得超5個贊
#!/usr/bin/python
# -*- coding: utf-8 -*-
import random
# generate an unsorted list
def generate_unsorted_list(num):
unsorted_list = []
for i in range(0, num):
unsorted_list.append(random.randint(0, 30))
print unsorted_list
return unsorted_list
def binary_search(target, sorted_list):
list_length = len(sorted_list)
start, end = 0, list_length-1
if list_length == 0:
print 'empty list'
return -1
while start < end:
middle = (start+end)/2
if target == sorted_list[middle]:
print 'find index:', middle
return middle
elif target < sorted_list[middle]:
end = middle-1
else:
start = middle+1
print 'not find'
return -1
if __name__ == "__main__":
unsorted_list = generate_unsorted_list(20)
sorted_list = sorted(unsorted_list)
print sorted_list
binary_search(14, sorted_list)
添加回答
舉報
0/150
提交
取消