二分查找（Binary Search）算法，也叫折半查找算法。二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

二分查找的递归与非递归实现

  1. function baearch(a, n, value) {
  2.   let low = 0;
  3.   let high = n - 1;
  5.   while(low <= high) {
  6.     let mid = low + ((high - low) >> 1);
  7.     if (a[mid] === value) {
  8.       return mid;
  9.     } else if (a[mid] < value) {
  10.       low = mid + 1;
  11.     } else {
  12.       high = mid - 1;
  13.     }
  14.   }
  15.   return -1;
  16. }

容易出错的 3 个地方。

1. 循环退出条件

注意是 low<=high，而不是 low<high。

2.mid 的取值。

实际上，mid=(low+high)/2 这种写法是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。改进的方法是将 mid 的计算方式写成 low+(high-low)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。

3.low 和 high 的更新

low=mid+1，high=mid-1。注意这里的 +1 和 -1，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。比如，当 high=3，low=3 时，如果 a[3]不等于 value，就会导致一直循环不退出

  1. function bsearch(a, n, value) {
  2.   return bsearchInternally(a, 0, n -1, value);
  3. }
  5. function bsearchInternally(a, low, high, value) {
  6.   if (low > high) return -1;
  7.   let mid = low + ((high - low) >> 1);
  9.   if (a[mid] === value) {
  10.     return mid;
  11.   } else if (a[mid] < value) {
  12.     return bsearchInternally(a, mid + 1, high, value);
  13.   } else {
  14.     return bsearchInternally(a, low, mid - 1, value);
  15.   }
  16. }

查找第一个值等于给定值的元素

  2. function bsearch(a, n, value) {
  3.   let low = 0;
  4.   let high = n - 1;
  6.   while(low <= high) {
  7.     let mid = low + ((high - low) >> 1);
  8.     if (a[mid] > value) {
  9.       hight = mid - 1;
  10.     } else if (a[mid] < value) {
  11.       low = mid + 1;
  12.     } else {
  13.       if ((mid === 0) || (a[mid - 1] !== value)) {
  14.         return mid;
  15.       } else {
  16.         high = mid - 1;
  17.       }
  18.     }
  19.   }
  20.   return -1;
  21. }

二分查找应用场景的局限性

首先，二分查找依赖的是顺序表结构，简单点说就是数组。二分查找算法需要按照下标随机访问元素。

其次，二分查找针对的是有序数据。
二分查找对这一点的要求比较苛刻，数据必须是有序的。如果数据没有序，我们需要先排序。

再次，数据量太小不适合二分查找。
如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。比如我们在一个大小为 10 的数组中查找一个元素，不管用二分查找还是顺序遍历，查找速度都差不多。只有数据量比较大的时候，二分查找的优势才会比较明显。
不过，这里有一个例外。如果数据之间的比较操作非常耗时，不管数据量大小，都推荐使用二分查找。比如，数组中存储的都是长度超过 300 的字符串，如此长的两个字符串之间比对大小，就会非常耗时。我们需要尽可能地减少比较次数，而比较次数的减少会大大提高性能，这个时候二分查找就比顺序遍历更有优势。

最后，数据量太大也不适合二分查找。

二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。比如，我们有 1GB 大小的数据，如果希望用数组来存储，那就需要 1GB 的连续内存空间。