[算法01] Binary Search
文章目录
Binary Search二分查找
作用:二分查找适用于有序的的数组或列表中,如果列表及数组中有n个元素,通过二分查找查询某一元素的位置需要的步骤是log(n)(注:该log的底数是2);
Python实现
def binary_search(list,item):
low = 0
high = len(list)-1 #python数组ID从0开始,与matlab不同、
t = 0
while low <= high:
t = t + 1;
mid = round((low + high)/2)
guess = list[mid]
if guess == item:
return (mid,t)
if guess > item:
high = mid-1
else:
low = mid + 1
return None #python关键字None,相当于matlab的NaN
my_list = range(1,101)
value = binary_search(my_list,1)
print ("Search Num:",value[1],'Index Position',value[0])
运行后结果:
Search Num: 6 Index Position 0
注意事项
- python定义的函数、使用如if、while、for时在语句后使用分号';'
- 列表元素索引从0开始;
- 如果定义的函数具有返回值,那么返回值通过关键字'return'实现函数输出,可多输出,如果调用函数返回值,可通过查询对应返回值索引,查找所需的函数返回值;
- 求中间索引位置时,防止出现查询调用时索引计算出现小数,通过round函数进行四舍五入处理;
Matlab实现
function [count,out] = binary_search(list,item)
%list:所要查找的数组一维行向量
%item:查找的元素
low = 1;
high = length(list);
t = 0;
while low <= high
t = t+1;
mid = round((low+high)/2);
guess = list(1,mid);
if guess == item
out = mid;
count = t;
break;
else if guess > item
high = mid - 1;
if high<low
out = 'None';
break;
end
else
low = mid + 1;
if high<low
out = 'None';
break;
end
end
end
end
注意事项
- Matlab数组元素索引从1开始,这点与python不同;
- 函数返回值在定义函数时直接定义;
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论