# 二分查找

# 概述

二分查找（Binary Search）是一种高效的查找算法，适用于已排序的数组。它通过不断将查找范围缩小一半来快速定位目标元素，时间复杂度为 O(log n)。

# 算法原理

前提条件：数组必须是有序的（升序或降序）
基本思想：
- 从数组的中间元素开始搜索
- 如果目标值等于中间元素，则找到目标
- 如果目标值小于中间元素，则在左半部分继续查找
- 如果目标值大于中间元素，则在右半部分继续查找
- 重复上述过程，直到找到目标或查找范围为空

# 代码实现

# 基础版本

function searchHandle(arr, target) {
  let left = 0
  let right = arr.length - 1
  while (left <= right) {
    let middle = Math.floor(left + (right - left) / 2)
    if (arr[middle] > target) {
      right = middle - 1
    } else if (arr[middle] < target) {
      left = middle + 1
    } else {
      return middle
    }
  }
  return -1
}

// 使用示例
const arr = [-1, 0, 1, 2, 3, 4, 5, 6]
const search = searchHandle(arr, 1)
console.log('search', search) // 输出：2

# 代码解析

left 和 right：定义查找范围的左右边界
middle：计算中间位置，使用 Math.floor(left + (right - left) / 2) 避免溢出
比较逻辑：
- arr[middle] > target：目标在左半部分，调整 right
- arr[middle] < target：目标在右半部分，调整 left
- arr[middle] === target：找到目标，返回索引
返回值：找到返回索引，未找到返回 -1

# 使用场景

# ✅ 适用场景

大规模有序数据查找：如字典、电话簿等
需要频繁查找的场景：一次排序，多次查找
内存受限的环境：只需要常数额外空间 O(1)

# ❌ 不适用场景

无序数组：需要先排序，增加时间成本
链表结构：无法随机访问，无法高效计算中间位置
小规模数据：简单遍历可能更高效
频繁插入删除的场景：维护有序性成本高

# 性能分析

指标	复杂度	说明
时间复杂度	O(log n)	每次查找范围减半
空间复杂度	O(1)	迭代实现，只使用常数个变量
最好情况	O(1)	第一次就找到目标
最坏情况	O(log n)	查找到最后一个元素或不存在
平均情况	O(log n)	期望查找次数为 log₂n

# 变体与扩展

# 1. 递归实现

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1
  
  const middle = Math.floor(left + (right - left) / 2)
  
  if (arr[middle] === target) {
    return middle
  } else if (arr[middle] > target) {
    return binarySearchRecursive(arr, target, left, middle - 1)
  } else {
    return binarySearchRecursive(arr, target, middle + 1, right)
  }
}

# 2. 查找第一个等于目标值的位置

function findFirstEqual(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1
  
  while (left <= right) {
    let middle = Math.floor(left + (right - left) / 2)
    
    if (arr[middle] === target) {
      result = middle
      right = middle - 1 // 继续在左半部分查找
    } else if (arr[middle] > target) {
      right = middle - 1
    } else {
      left = middle + 1
    }
  }
  
  return result
}

# 3. 查找最后一个等于目标值的位置

function findLastEqual(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1
  
  while (left <= right) {
    let middle = Math.floor(left + (right - left) / 2)
    
    if (arr[middle] === target) {
      result = middle
      left = middle + 1 // 继续在右半部分查找
    } else if (arr[middle] > target) {
      right = middle - 1
    } else {
      left = middle + 1
    }
  }
  
  return result
}

# 4. 查找第一个大于等于目标值的位置

function findFirstGreaterOrEqual(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1
  
  while (left <= right) {
    let middle = Math.floor(left + (right - left) / 2)
    
    if (arr[middle] >= target) {
      result = middle
      right = middle - 1
    } else {
      left = middle + 1
    }
  }
  
  return result
}

# 注意事项

# 📝 最佳实践

明确查找目标：确定是精确匹配还是范围查找
注意数组顺序：升序还是降序会影响比较逻辑
处理边界情况：空数组、单元素数组、目标不存在等
选择合适的变体：根据具体需求选择标准版或变体版本

本章目录