前提:数组已预先排序。 目标:查找数组中指定数字的坐标(0-based)。
二分法通俗点说,就是对一个已经事先排序过的数组,设置分别指向数组首尾两头的首尾游标,然后根据首尾游标的位置设定中间点游标,由于数组已经排序过了,可以通过比较给定数字与三个游标的大小关系来不断的更新首尾中三个游标的位置,这个过程中只要收尾中三个游标对应的数字有一个等于给定数字,或者首尾游标的位置中间仅剩一个游标位,就可以拿到给定数字对应的位置的。
function binarySearch (arr, num) { // assume arr has been sorted in advance var low = 0 var high = arr.length - 1 var mid = Math.floor((low + high) / 2) // 循环的终止条件是high - low长度等于1,或遍历期间直接取到了目标数字 // 因为目标是找到指定数字在原数组中的下标,所以采用递归拆数组的思路反而不方便 while (high - low > 1) { if (num === arr[low]) { return low } else if (num === arr[high]) { return high } else if (num === arr[mid]) { return mid } else if (num > arr[mid]) { low = mid mid = Math.floor((low + high) / 2) } else { high = mid mid = Math.floor((low + high) / 2) } } // if not found return -1 }
最新评论
大哥资深网民啊,01年我还在念小学。。
看着有点难过。。。
嘿嘿,谢谢老哥,也祝老哥事业蒸蒸日上。
我是你唯一的药学类友情链接网站。 作为一个80后的过来人祝福你,生活越来越好。
这篇文章,我们中学那会老师课堂上念给我们听的。
哈哈哈哈哈,没想到啊, 我有手抄版
嗯,是的
好心办坏事多了去啦
哈哈,是的,我15年末来上海写代码了,一晃三年多过去了,好快。
今天看QQ好友的时候突然看到了你的名字,想起几年前在药品国际注册群挺活跃/厉害的你,现在不见踪影了。就搜了一下,没想到你现在转行去写代码了... (刚才打漏了一句话...)