js实现二分法查找方法

JavaScript016

js实现二分法查找方法,第1张

所谓二分法查找法,也就是折半查找,它是一种在有序数组查找特定元素的搜索算法。

参考《前端程序员面试秘籍》

思想:从数组中开始查找,如果该元素是要搜索的目标元素,则循环结束,如果不是继续下一步,如果目标元素大于或者小于中间元素,则在数组大于或者小于中间元素的那一半区域进行查找,进而重复上面操作。如果数组是空的,则找不到该目标元素。

问题在于这句:

middle=Math.ceil((left+right)/2)

ceil是向上取整。

假设数组为双数的长度时,到倒数第二次运算时,就是left=right了,这时计算的middle=left+1,这样在下一次计算时就出现left大于right的情况了