Skip to content

二分查找

· 3 min

基础知识#

二分查找，英语为 Binary Search，这是一种高效的 查找 算法，适用于在 已排序 的数组中快速定位目标元素。其核心思想是通过每次将查找范围缩小一半，逐步逼近目标值，从而实现快速查找。

1-100 之间想好了一个数，来猜这个数，每次猜测后，我会告诉你大了还是小了。

二分查找的基本步骤如下：

  1. 初始化查找区间： 设置两个指针，left 和 right，分别指向数组的起始和结束位置。

  2. 计算中间位置： 在每次查找中，计算当前查找区间的中间索引 mid，通常使用 Math.floor((left + right) / 2) 来避免浮点数误差。

  3. 比较中间元素与目标值：

    • 如果 arr[mid] 等于目标值，则查找成功，返回 mid
    • 如果 arr[mid] 小于目标值，则目标值位于右半部分，更新 left = mid + 1
    • 如果 arr[mid] 大于目标值，则目标值位于左半部分，更新 right = mid - 1

  4. 重复上述过程： 直到找到目标值或 left 超过 right，表示查找失败，返回 -1

代码实现#

  1. 迭代实现
function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1


  while (left <= right) {
    // 可以进行查找
    // 根据 left 和 right 计算出中间的下标
    const mid = Math.floor((left + right) / 2)


    // 中间下标所对应的元素和目标值进行比较
    if (arr[mid] === target) {
      // 说明找到了
      return mid
    } else if (arr[mid] < target) {
      // 目标值在右半部分区域，更新 left
      left = mid + 1
    } else {
      // 目标值在左半部分区域，更新 right
      right = mid - 1
    }
  }
  // 思考：什么时候退出 while
  // 当 left 大于 right 的时候，会退出 while
  // 说明没有找到
  return -1
}


const arr = [4, 7, 9, 11, 20, 24, 30, 41]
const target1 = 30
const target2 = 70


console.log(binarySearch(arr, target1)) // 6
console.log(binarySearch(arr, target2)) // -1
  1. 递归实现
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    // 没有找到时递归的出口
    return -1
  }


  const mid = Math.floor((left + right) / 2)


  if (arr[mid] === target) {
    // 找到的时候，递归的出口
    return mid
  } else if (arr[mid] < target) {
    // 说明目标值在右边
    return binarySearch(arr, target, mid + 1, right)
  } else {
    // 说明目标值在左边
    return binarySearch(arr, target, left, mid - 1)
  }
}


const arr = [4, 7, 9, 11, 20, 24, 30, 41]
const target1 = 30
const target2 = 70


console.log(binarySearch(arr, target1)) // 6
console.log(binarySearch(arr, target2)) // -1

复杂度#

-EOF-