Published on

二分查找算法

Authors
  • avatar
    Name
    谢克成
    Twitter

二分查找算法

二分查找算法（Binary Search）是一种高效的搜索算法，用于在有序数组中查找特定元素。它的核心思想是通过将查找区间逐步缩小一半，从而快速定位目标元素的位置。以下是 JavaScript 版本的二分查找算法的概要总结：

算法步骤：

  1. 确定查找区间的起始和结束位置：将起始位置 low 初始化为 0，将结束位置 high 初始化为数组长度减 1。
  2. 进入循环：使用循环（通常是while循环）来执行以下步骤，直到查找区间为空或者找到目标元素。
  3. 计算中间位置：计算中间位置 mid，可以通过 (low + high) / 2 来获取。这将帮助确定下一步是在左半部分还是右半部分查找。
  4. 比较目标元素：将目标元素与位于中间位置的元素进行比较。
    • 如果目标元素等于中间位置的元素，查找成功，返回中间位置。
    • 如果目标元素小于中间位置的元素，说明目标元素位于左半部分，将 high 更新为 mid - 1。
    • 如果目标元素大于中间位置的元素，说明目标元素位于右半部分，将 low 更新为 mid + 1。
  5. 重复步骤 2-4，直到查找区间为空或找到目标元素为止。

算法特点：

  • 二分查找算法适用于有序数组，因为它利用了数组的有序性来减少搜索范围。
  • 它的时间复杂度为 O(log n)，其中 n 是数组的长度。这使得它比线性搜索更加高效，特别是对于大型数组。
  • 二分查找要求数组中的元素是可比较的，因此适用于基本数据类型和自定义对象（需要提供比较函数）。

JavaScript 示例代码：

function binarySearch(arr, target) {
  let low = 0
  let high = arr.length - 1

  while (low <= high) {
    let mid = Math.floor((low + high) / 2)

    if (arr[mid] === target) {
      return mid // 找到目标元素，返回索引
    } else if (arr[mid] < target) {
      low = mid + 1 // 在右半部分查找
    } else {
      high = mid - 1 // 在左半部分查找
    }
  }

  return -1 // 没有找到目标元素
}

// 示例用法
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15]
const targetElement = 7
const index = binarySearch(sortedArray, targetElement)
if (index !== -1) {
  console.log(`目标元素 ${targetElement} 位于索引 ${index}`)
} else {
  console.log(`未找到目标元素 ${targetElement}`)
}
• View on GitHub