算法笔记系列:二分查找
它是一种常用的且效率较高的查找方法。使用该算法对被查找对象有两点要求:1. 必须采用顺序存储结构;2. 必须按关键字大小有序排列。即如果对象已经有序,才会考虑使用二分查找。
示例(查找1个数):
function binarySearch(arr, target) {
var l = 0,
r = arr.length - 1,
m;
while (l <= r) {
m = Math.floor(l + (r - l) / 2);
if (arr[m] === target) return m;
if (arr[m] < target) l = m + 1;
else r = m - 1;
}
return -1;
}