码海

# 二分搜索

比较次数: 0

# 算法原理

二分搜索（Binary Search）是一种高效的搜索算法，它利用数据的有序性，通过将搜索范围逐步缩小一半来定位目标元素。每次比较中间元素与目标值，根据比较结果决定在哪一半继续搜索，直到找到目标元素或确定元素不存在。

# 算法步骤

  1. 确保数组已经排序
  2. 设置左边界left = 0和右边界right = length - 1
  3. 当left <= right时，重复以下步骤：
    • 计算中间位置mid = (left + right) / 2
    • 如果中间元素等于目标值，返回mid
    • 如果中间元素大于目标值，在左半部分搜索，right = mid - 1
    • 如果中间元素小于目标值，在右半部分搜索，left = mid + 1
  4. 如果未找到目标值，返回-1

# 代码实现

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    // 避免整数溢出的写法
    const mid = left + Math.floor((right - left) / 2);
    
    if (arr[mid] === target) {
      return mid;  // 找到目标值
    } else if (arr[mid] > target) {
      right = mid - 1;  // 在左半部分继续搜索
    } else {
      left = mid + 1;   // 在右半部分继续搜索
    }
  }
  
  return -1;  // 未找到目标值
}

// 递归版本的二分搜索
function recursiveBinarySearch(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return -1;
  }
  
  const mid = left + Math.floor((right - left) / 2);
  
  if (arr[mid] === target) {
    return mid;
  } else if (arr[mid] > target) {
    return recursiveBinarySearch(arr, target, left, mid - 1);
  } else {
    return recursiveBinarySearch(arr, target, mid + 1, right);
  }
}

# 复杂度分析

# 时间复杂度

  • 最好情况：O(1)，目标元素在中间位置
  • 最坏情况：O(log n)，需要多次折半
  • 平均情况：O(log n)

# 空间复杂度

  • 迭代版本：O(1)
  • 递归版本：O(log n)，由于递归调用栈的开销

# 算法特点

# 优点

  • 时间复杂度低，效率高
  • 适用于大规模数据搜索
  • 实现简单，容易理解

# 缺点

  • 要求数据必须有序
  • 只适用于支持随机访问的数据结构（如数组）
  • 对于小规模数据，可能不如线性搜索

# 适用场景

  1. 在大规模有序数据集中查找元素
  2. 需要频繁进行查找操作
  3. 数据集较为稳定，排序成本可以分摊

# 变体和应用

  1. 查找第一个等于目标值的元素
  2. 查找最后一个等于目标值的元素
  3. 查找第一个大于等于目标值的元素
  4. 查找最后一个小于等于目标值的元素
// 查找第一个等于目标值的元素
function searchFirstEqual(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    
    if (arr[mid] > target) {
      right = mid - 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      // 找到目标值，但需要确认是否为第一个
      if (mid === 0 || arr[mid - 1] !== target) {
        return mid;
      }
      right = mid - 1;
    }
  }
  
  return -1;
}

// 查找第一个大于等于目标值的元素
function searchFirstGreaterEqual(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    
    if (arr[mid] >= target) {
      if (mid === 0 || arr[mid - 1] < target) {
        return mid;
      }
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  
  return -1;
}

# 实际应用

  1. 在数据库索引中快速定位记录
  2. 在有序数组中进行快速查找
  3. 在二分图匹配中寻找最优解
  4. 在机器学习中的模型参数优化

← 广度优先搜索 →