JS里的二分法查询-Brooks' Forest

什么是二分法查询？

二分法查询（Binary Search）是一种在**有序数组**中快速查找特定元素的高效算法。它通过每次比较将搜索范围缩小一半，时间复杂度为O(log n)，远优于线性查找的O(n)。

实现原理

确定数组的中间元素
如果目标值等于中间元素，则返回索引
如果目标值较小，则在左半部分继续查找
如果目标值较大，则在右半部分继续查找
重复直到找到目标或搜索范围为空

JavaScript实现

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]

console.log(binarySearch(sortedArray, 9)) // 输出: 4

console.log(binarySearch(sortedArray, 2)) // 输出: -1

递归实现版本

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

使用场景

大型有序数据集查找
需要频繁查询的静态数据集
内存受限环境（相比哈希表更省空间）

注意事项

数组必须是有序的（升序或降序）
对于小型数据集，线性查找可能更简单高效
JavaScript的数组方法如indexOf使用线性查找

性能比较

方法	时间复杂度	适用场景
线性查找	O(n)	小型/无序数组
二分法查找	O(log n)	大型有序数组
哈希表查找	O(1)	需要极快查询速度

总结

二分法查询是处理有序数组的强大工具，虽然实现比线性查找稍复杂，但其优异的性能在大数据量场景下优势明显。掌握这一算法将显著提升你在处理有序数据时的效率。

提示：现代JavaScript引擎提供了TypedArray等优化数据结构，在处理数值型有序数据时性能更佳。

思考

因为二分法的必要前提是数据已经排序，那么考虑到在数据较多较大时排序已经是不低的消耗，那么应该如何处理这个矛盾呢？

《二分法需要预排序情况下的成本考虑》

目录CONTENT

JS里的二分法查询