如果你查找的数据是有序的，二分查找比顺序查找算法更高效。

自然语言描述

要理解二分查找算法的原理，可以想象一下玩猜数字游戏的时候，这个数字在 1-100 之间，而要猜的数字由你的朋友决定。游戏规则是你每猜一个数字，你的朋友将会做出一下三种回应中的一种：

  • 猜对了
  • 大了
  • 小了

根据以上规则，最快猜中的方法是 每一次猜中间的数值。

这个策略就是二分查找算法。这个算法只对有序的数据集有效。

  • 将数组的第一个位置设置为下边界
  • 将数组的最后一个元素所在位置设置为上边界
  • 若下边界等于或小于上边界
    • 将中点设置为 【（上边界 + 下边界）除以 2】 的值，向下取整
    • 如果中点元素小于查询值，则下边界设置为中点元素所在下标加 1
    • 如果中点元素大于查询值，则上边界设置为中点元素所在下标减 1
    • 否则中点元素就是要查询的值，直接返回中点元素的下标

二分查找算法实现

查找成功返回下标，失败返回 -1

  1. function binSearch(arr, data) {
  2.   let upper = arr.length - 1
  3.   let lower = 0
  4.   while (lower <= upper) {
  5.     let mid = Math.floor((upper + lower) / 2)
  7.     if (arr[mid] < data) {
  8.       lower = mid + 1
  9.     } else if (arr[mid] > data) {
  10.       upper = mid - 1
  11.     } else {
  12.       return mid
  13.     }
  14.   }
  15.   return -1
  16. }

计算重复次数

当 binSearch 函数找到某个值时，如果在数据集中还有其他相同的值出现，那么该函数会定位在类似值的附近。也就是说，其他相同的值，只会出现在已找到值的左边或右边。

我们可以通过两个循环来实现，一个向左循环遍历，查找左边的，另一个向右循环遍历，查找右边的

  1. function count(arr, data) {
  2.   let count = 0
  3.   let position = binSearch(arr, data)
  5.   if (position === -1) return count
  7.   count++
  9.   for (let i = position + 1; i > 0; i--) {
  10.     if (arr[i] === data) {
  11.       count++
  12.     } else {
  13.       break
  14.     }
  15.   }
  16.   for (let i = position + 1; i < arr.length; i++) {
  17.     if (arr[i] === data) {
  18.       count++
  19.     } else {
  20.       break
  21.     }
  22.   }
  23. }