JS 【算法】二分查找

使用场景

在有序数组中查找目标元素

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.lengthif (length === 0) return -1let 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.lengthif (length === 0) return -1// 开始和结束的范围if (startIndex == null) startIndex = 0if (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}}