二分查找简介

快速概览

二分查找是一种重要的搜索算法，对于技术面试和项目中可能遇到的搜索问题都非常重要。对于大型数组，该算法速度非常快。唯一的限制是它只能用于已排序的数组。

电话簿类比

很多人想到二分查找时，喜欢联想到翻电话簿。虽然现在大多数人都是直接在手机通讯录里查找联系人，这种比喻略显过时，但我认为这仍然是理解二分查找概念的一个好方法。

如果你要在电话簿里查找一个姓氏，比如史密斯，你会怎么做呢？大多数人会先翻到他们认为这个姓氏可能出现的地方，大概在电话簿中间偏后的位置。然后他们会查看翻到的那一页上的姓氏。假设你翻到一页，上面都是以字母 P 开头的姓氏。你知道 P 在 S 前面，所以你需要查看电话簿的后半部分。因此，你可以排除从电话簿开头到你当前所在页面之前的所有姓氏，因为你知道史密斯不在那一页上。

你会重复这个过程，在电话簿剩余部分大约中间的位置搜索，并将名字与你的目标名字“史密斯”进行比较，直到找到包含你要查找的名字的那一页。

这与二分查找的工作原理非常相似，也解释了为什么它比逐个查找元素快得多。由于数据已经排序，我们可以更准确地估计目标值的位置。

正在编写伪代码

了解了算法之后，我们就可以开始编写算法的伪代码了。假设我们要5在数组中查找目标值[0, 1, 2, 3, 5, 7, 8]：

我们知道函数应该接受两个参数：一个已排序的数组和一个要在数组中查找的目标值。我们知道每次都会查看数组中间的元素，并将其与目标值进行比较。如果没有找到匹配项，我们就知道需要查看数组的新部分，要么是中间元素之后的部分，要么是中间元素之前的部分。

找到数组中间位置的一个好方法是使用平均值。要找到平均值，我们需要指向当前“研究”部分数组左右两侧的指针。我们需要将这两个指针相加，然后除以二。因此，我们将存储当前查看部分数组最左侧的索引以及最右侧的索引。

接下来，我们将创建一个循环，以便持续遍历数组的不同部分，直到找到匹配项。每次循环中，我们将计算当前遍历数组部分的中间索引，并将该索引处的值与目标值进行比较。如果中间值与目标值匹配，则返回该中间值的索引。如果中间值小于目标值，则将左指针指向当前中间值上方 1 个索引的位置，以查看当前作用域数组的后半部分。如果中间值大于目标值，则将右指针指向当前中间值下方 1 个索引的位置，以查看当前作用域数组的前半部分。然后，我们将再次执行循环。

如果在搜索整个数组后仍然找不到匹配项，那么我们将返回 -1，表示没有找到目标值的索引。

以下是我们目前为止编写的一些伪代码：

function binarySearch(sortedArray, targetValue) {
  //set leftSide to beginning of array at first
  let leftSide = 0
  //set rightSide to end of array at first so the entire array is in scope
  let rightSide = endOfArray

  while (targetNotFound) {
    // average the left and right pointer to find middle. Will need to round this number to get an integer
    let middle = average(left, right)

    if (targetValue === valueAtMiddleIndex) {
      return middle
    } else if (valueAtMiddleIndex < targetValue) {
      leftSide = middle + 1
    } else if (valueAtMiddleIndex > targetValue) {
      rightSide = middle - 1
    }
  }
  // if target value can't be found in array
  return -1
}

让我们通过测试用例来逐步分析代码。

• 我们从……开始[0, 1, 2, 3, 5, 7, 8]，并正在寻找……5
• leftSide将在 处初始化0。rightSide将在 处初始化6。
• 第一次循环：
  • middle初始化于3
  • 索引处的元素3是3
  • 3===吗5？不，它比目标值小。
  • leftSide现在 = 3 + 1 =4
• 第二循环：
  • 我们现在正在查看数组的这一部分：[5, 7, 8]
  • middle现在 = (4 + 6) / 2 =5
  • 索引处的元素5是7
  • 7===吗5？不，它比目标大。
  • rightSide现在 = 5 - 1 =4
• 第三循环：
  • 现在我们只关注这一部分：[5]
  • middle现在 = (4 + 4) / 2 =4
  • 索引处的元素4是5
  • 是否5=== 5。是的！
  • 返回middle哪个 =4

有用！

问题

你觉得这段伪代码有问题吗？

如果你认为在某些情况下循环会无限循环下去，那就对了。在我们目前的代码中，只有找到目标值时才会停止循环；但如果始终找不到目标值，循环就会一直进行下去。

避免循环的一个好方法是确保左指针永远不会超过右指针。也就是说，如果数组只剩下一个值需要检查，并且该值不等于目标值，则退出循环。以下是更新后的伪代码：

function binarySearch(sortedArray, targetValue) {
  //set leftSide to beginning of array at first
  let leftSide = 0
  //set rightSide to end of array at first so the entire array is in scope
  let rightSide = endOfArray

  // exit loop if left pointer goes past rightPointer. I removed the targetNotFound condition since the return statement within the loop already handles this.
  while (leftSide <= rightSide) {
    // average the left and right pointer to find middle. Will need to round this number to get an integer
    let middle = average(left, right)

    if (targetValue === valueAtMiddleIndex) {
      return middle
    } else if (valueAtMiddleIndex < targetValue) {
      leftSide = middle + 1
    } else if (valueAtMiddleIndex > targetValue) {
      rightSide = middle - 1
    }
  }
  // if target value can't be found in array
  return -1
}

让我们使用与之前相同的数组，但目标值改为新的值，来逐步分析伪代码4。

• 我们从……开始[0, 1, 2, 3, 5, 7, 8]，并正在寻找……4
• leftSide将在 处初始化0。rightSide将在 处初始化6。
• 第一次循环是因为 leftSide( 0)和<=rightSide( 6)：
  • middle初始化于3
  • 索引处的元素3是3
  • 3===吗4？不，它比目标值小。
  • leftSide现在 = 3 + 1 =4
• 第二次循环是因为 leftSide( 4)和<=rightSide( 6)：
  • 我们现在正在查看数组的这一部分：[5, 7, 8]
  • middle现在 = (4 + 6) / 2 =5
  • 索引处的元素5是7
  • 7===吗4？不，它比目标大。
  • rightSide现在 = 5 - 1 =4
• 第三次循环，因为 leftSide( 4)和<=rightSide( 4)：
  • 现在我们只关注这一部分：[5]
  • middle现在 = (4 + 4) / 2 =4
  • 索引处的元素4是5
  • 是否5=== 4？不，它比目标大。
  • rightSide现在 = 4 - 1 =3
• 退出 while 循环，因为 leftSide( 4) 不等于<=rightSide( 3)。
• 返回-1

有用！

这段伪代码已经非常接近实际代码了，但我建议你在继续之前先自己写出一个能运行的 JavaScript 函数。为了防止你偷看下面的代码，我放了一个 GIF 动画。

我实现的二分查找

以下是我用 JavaScript 实现的该算法：

function binarySearch(sortedArr, value){
  let left = 0;
  let right = sortedArr.length - 1;

  // I chose to initialize these variables outside the loop
  let middle;
  // currentElem will be the element that is at the middle index
  let currentElem;

  while (right >= left) {
      // Math.floor() will round the decimal down to the nearest integer
      middle = Math.floor((left + right) / 2)

      currentElem = sortedArr[middle];

      if (currentElem === value) {
          return middle;
      } else if (currentElem < value) {
          left = middle + 1;
      } else if (currentElem > value) {
          right = middle - 1;
      }
  }
  return -1;
}

二分查找的大O

Big O 表示法的最坏情况性能为 O(log n)，速度非常快。作为对比，大多数 JavaScript 内置的搜索方法（例如 `get_search()`）的Array.prototype.includes()时间复杂度为 O(n)，因为它们使用的是线性搜索。

对于非小型数组，二分查找比线性查找快得多。但如果数组很小，二分查找的速度可能不如线性查找。我发现二分查找唯一的缺点是数据必须排序。

干杯

感谢阅读。希望今天我能教给你一些新知识，也祝大家周末愉快平安！

资源

• Colt Steele 的 JavaScript 算法和数据结构大师班
• 时间复杂度图