vlambda博客
学习文章列表

算法笔记系列:二分查找

二分查找(基础篇)

它是一种常用的且效率较高的查找方法。使用该算法对被查找对象有两点要求:1. 必须采用顺序存储结构;2. 必须按关键字大小有序排列。即如果对象已经有序,才会考虑使用二分查找。

:将序列(已有序)中的元素(n个)从整体的中间部分一分为二,并取n/2处的元素(m)与查找目标x做比较,如果m与x相等,则查找完成,算法终止。否则,如果x<m,只需在当前两部分的左半区间内继续查找;如果x>m,只需在其右半区间内继续查找。重复上述分/查操作,直至找到x或全部元素已完成比较却未找到x。

示例(查找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;}