2.二分搜索（Binary Search）

认识

二分搜索，也叫折半搜索，是一种在有序数组中查找特定元素的搜索算法。所以是用二分查找的前提是数组必须是有序的.

二分搜索通过不断将搜索范围减半的方式，快速定位目标元素。

工作原理

1. 从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束
2. 如果目标元素大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找
3. 重复上述过程，直到找到目标元素或搜索范围为空

时间复杂度

• 最坏情况：O(log n)
• 平均情况：O(log n)
• 最好情况：O(1)（目标元素正好在中间）

空间复杂度

• 迭代实现：O(1)
• 递归实现：O(log n)（由于递归调用栈）

实现

基础版本

基础版本实现，这里我们先来自己手写一个简单的二分搜索模块

     /**
     * 1-基础迭代二分搜索
     * @param {Array} arr - 已排序的数组
     * @param {*} target - 要查找的目标元素
     * @return {number} 目标元素的索引，如果未找到则返回-1
     */
    function binarySearch(arr,target){
        let left=0;
        let right=arr.length-1;
        while(left <= right){
            const mid=Math.floor((left+ right)/2);
            if(arr[mid]===target){
                return mid;// 找到目标，返回索引
            }else if(arr[mid]< target){
                left = mid +1; // 目标在右半部分
            }else{
                right =mid -1;  // 目标在左半部分
            }
        }
        return -1;
    }

    // 使用示例
    const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
    console.log(binarySearch(sortedArray, 7)); // 输出: 3
    console.log(binarySearch(sortedArray, 8)); // 输出: -1

防止整数溢出

接下来我们就跟着trae优化迭代上面版本的二分搜索，有时候我们会出现一种情况

这里我们主要讲的就是left + (right - left) / 2 比 (left + right) / 2 更安全

当 left 和 right 都很大时
和可能会超过 JavaScript 中 Number 类型的最大安全整数（2^53 - 1）
这会导致整数溢出，得到错误的结果

利用下面的写法就可以有效避免我们结果超过Number.MAX_SAFE_INTEGER，也就是通过先计算的方式直接避免最后结果超过最大值

使用 left + (right - left) / 2

// 先计算 (right - left)，这个差值很小
// 然后加到 left 上，不会溢出

// left + right 会先计算，结果可能超过 Number.MAX_SAFE_INTEGER
// 导致溢出，得到错误的结果

所以防止整数溢出我们更改为

// 修改前
const mid = Math.floor((left + right) / 2);

// 修改后
const mid = left + Math.floor((right - left) / 2);

添加输入验证

// 添加在函数开始处
// 输入验证
if (!Array.isArray(arr) || arr.length === 0) {
    throw new Error('输入必须是非空数组');
}

提前处理边界情况

// 添加在输入验证之后，循环之前
// 提前处理边界情况
if (arr[0] === target) return 0;
if (arr[arr.length - 1] === target) return arr.length - 1;

优化循环条件

// 修改前
while (left <= right) {

// 修改后
while (left < right) {

// 调整循环体内的逻辑

调整循环体内的逻辑

// 修改前
if (arr[mid] === target) {
    return mid; // 找到目标，返回索引
} else if (arr[mid] < target) {
    left = mid + 1; // 目标在右半部分
} else {
    right = mid - 1; // 目标在左半部分
}

// 修改后
if (arr[mid] < target) {
    left = mid + 1; // 目标在右半部分
} else {
    right = mid; // 目标在左半部分或mid就是目标
}

最后我们优化完成以后

function binarySearch(arr, target) {
  if (!Array.isArray(arr) || arr.length === 0) {
      throw new Error('输入必须是非空数组');
  }
  // 提前处理边界情况
  if (arr[0] === target) return 0;
  if (arr[arr.length - 1] === target) return arr.length - 1;
  let left = 0;
  let right = arr.length - 1;
  // 循环条件优化为 left < right
  while (left < right) {
      // 防止整数溢出的中间值计算
      const mid = left + Math.floor((right - left) / 2);

      if (arr[mid] < target) {
          left = mid + 1; // 目标在右半部分，排除mid
      } else {
          right = mid; // 目标在左半部分或mid就是目标
      }
  }
  // 循环结束后检查left位置是否为目标
  return arr[left] === target ? left : -1;
}