在计算机科学中，二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
复杂度分析
时间复杂度：
折半搜索每次把搜索区域减少一半，时间复杂度为
。（n代表集合中元素的个数）
空间复杂度：
虽以递归形式定义，但是尾递归，可改写为循环。
Ruby代码示例
def binseaech(arr, i)
low, high = 0, arr.size - 1
while (low < high)
mid = (low + high)/2
if arr[mid] < i
low = mid + 1
elsif arr[mid] > i
high = mid - 1
else
return mid
end
end
end
arr = [1,3,12,34,35,46,91,108]
puts binseaech(arr, 91)
结果：
6 [Finished in 0.1s]
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！
如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
内蒙古资源网 Copyright www.nmgbbs.com
暂无“Ruby实现二分搜索(二分查找)算法的简单示例”评论...
P70系列延期，华为新旗舰将在下月发布
3月20日消息，近期博主@数码闲聊站 透露，原定三月份发布的华为新旗舰P70系列延期发布，预计4月份上市。
而博主@定焦数码 爆料，华为的P70系列在定位上已经超过了Mate60，成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢？
根据目前爆料的消息来看，华为P70系列将推出三个版本，其中P70和P70 Pro采用了三角形的摄像头模组设计，而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智，但辨识度绝对拉满。