时间复杂度 O(logn)
使用场景
在有序数组中查找目标元素
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] const target = 2 console.log(binarySearch1(arr, target)) console.log(binarySearch2(arr, target))
循环实现
function binarySearch1(arr, target) { const length = arr.length if (length === 0) return -1 let startIndex = 0 // 开始位置 let endIndex = length - 1 // 结束位置 while (startIndex <= endIndex) { const midIndex = Math.floor((startIndex + endIndex) / 2) // 中间位置 const midValue = arr[midIndex] if (target < midValue) { // 目标值较小，则继续在左侧查找 endIndex = midIndex - 1 } else if (target > midValue) { // 目标值较大，则继续在右侧查找 startIndex = midIndex + 1 } else { // 相等，则返回 return midIndex } } return -1 // 未找到 }
递归实现
function binarySearch2(arr, target, startIndex, endIndex) { const length = arr.length if (length === 0) return -1 // 开始和结束的范围 if (startIndex == null) startIndex = 0 if (endIndex == null) endIndex = length - 1 // 开始和结束相遇，则结束 if (startIndex === endIndex) return -1 // 中间位置 const midIndex = Math.floor((startIndex + endIndex) / 2) const midValue = arr[midIndex] if (target < midValue) { // 目标值较小，则从左侧寻找 return binarySearch2(arr, target, startIndex, midIndex - 1) } else if (target > midValue) { // 目标值较大，则从右侧查找 return binarySearch2(arr, target, midIndex + 1, endIndex) } else { // 相等，则返回 return midIndex } }
