#!/usr/bin/python
""" 折半查找算法
"""
#定義函數(shù)
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"
#調(diào)用函數(shù)
arr = [10,20,30,40,50,60,70]
BinarySearch(arr, 40, len(arr))
3 回答
幕布斯7119047
TA貢獻(xiàn)1794條經(jīng)驗 獲得超8個贊
是這里middle = ( left + right ) / 2，求出來的是浮點數(shù)，應(yīng)該轉(zhuǎn)成int就可以了int(middle)
慕雪6442864
TA貢獻(xiàn)1812條經(jīng)驗 獲得超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)
湖上湖
TA貢獻(xiàn)2003條經(jīng)驗 獲得超2個贊
二分查找的寫法要看你的需求，對于arr = [40,40,40]你是希望返回0還是1還是2？或者你的假設(shè)根本不出現(xiàn)重復(fù)值？
添加回答
舉報
0/150
提交
取消