描述

二分查找算法的基本思想是将有序数组分为两部分,比较中间元素与目标值的大小,如果相等则返回,否则在较小或较大的部分继续查找。时间复杂度为 O(log n)。

步骤描述：

1. 根据数组长度获取中间值。
2. 用中间值去和目标值比较：
   1. 如果相等直接返回下标
   2. 如果中间值比目标值大，返回左半部分继续查找
   3. 如果目标值比中间值大，返回右半部分继续查找

// 函数主体
function binarySearch(array, target) {
  function searchIndex(left, right) {
    // 获取中间位置元素
    let centerIndex = Math.floor((left + right) / 2);
    // 如果中间值比目标值大，从左侧查找
    if (array[centerIndex] > target) {
      // 需要注意左侧查找的右边界值为 中间值下标 -1
      return searchIndex(left, centerIndex - 1);
      // 如果中间值比目标值小，从右侧查找
    } else if (array[centerIndex] < target) {
      // 需要注意右侧查找的左边界值为 中间值下标 + 1
      return searchIndex(centerIndex + 1, right);
    } else {
      // 如果相等，则直接返回下标
      return centerIndex;
    }
  }
  // 调用该递归函数
  return searchIndex(0, array.length - 1);
}
let temp = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let result = binarySearch(temp, 10);
console.log(result); // 10

更新日志

2025/8/24 08:17

查看所有更新日志

• e7112-1于 2025/8/24