二分查找算法是一种高效的搜索方法，可用于在有序数组中查找特定元素的位置。在前端开发中，二分查找算法常用于数据处理和优化算法。本文将介绍如何使用 ECMAScript 2021 实现 JavaScript 中的二分查找。
什么是二分查找算法？
二分查找算法又称为折半查找算法，是一种针对有序数组进行快速查找的算法。其基本思想是将搜索区间不断二分，缩小搜索范围，直到找到指定元素或搜索区间为空时停止搜索。
假设我们要查找有序数组 arr 中的元素 val，二分查找算法的流程如下：
- 初始化搜索区间 left 和 right，left = 0，right = arr.length - 1。
- 计算中间位置 mid，mid = (left + right) / 2。
- 如果 arr[mid] 等于 val，说明找到了指定元素，返回 mid。
- 如果 arr[mid] 大于 val，说明指定元素在左侧区间，更新 right 值为 mid - 1。
- 如果 arr[mid] 小于 val，说明指定元素在右侧区间，更新 left 值为 mid + 1。
- 重复步骤 2~5，直到找到指定元素或搜索区间为空。
二分查找算法的时间复杂度为 O(logn)，是一种非常快速的查找算法。
ECMAScript 2021 中的二分查找方法
ECMAScript 2021 引入了一个新的 Array 方法：Array.prototype.findIndex()，可以用来实现二分查找算法。该方法接受一个回调函数，用于定义搜索条件，具体语法如下：
arr.findIndex(callback[, thisArg])
其中，callback 是用于定义搜索条件的回调函数，其参数为当前元素的值、当前元素的索引和待搜索的数组。thisArg 是可选参数，用于指定 callback 函数中 this 的值。
下面是使用 Array.prototype.findIndex() 实现二分查找的示例代码：
function binarySearch(arr, val) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = (left + right) >> 1;
if (arr[mid] === val) {
return mid;
} else if (arr[mid] < val) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 没有找到指定元素
}
const arr = [1, 3, 5, 7, 9];
const val = 3;
console.log(binarySearch(arr, val)); // 输出 1，即元素 3 在数组中的索引位置在上面的代码中，我们定义了一个 binarySearch() 函数，该函数接受一个有序数组 arr 和待查找的元素 val，返回指定元素在数组中的索引位置。该函数通过 while 循环不断缩小搜索区间，并使用 Array.prototype.findIndex() 方法查找指定元素。
值得注意的是，在上面的示例代码中，我们使用 truncated division 运算符 >> 来计算 mid 值，该运算符可以将除以 2 的操作进行优化。如果使用 Math.floor() 计算 mid 值，则会降低代码执行速度。
总结
本文介绍了 ECMAScript 2021 中如何使用 Array.prototype.findIndex() 方法实现 JavaScript 中的二分查找算法。通过本文的介绍，我们可以清晰地了解到二分查找算法的基本思想和流程，并且掌握了在 ECMAScript 2021 中实现该算法的方法和技巧。二分查找是一种重要的搜索算法，在前端开发中具有广泛的应用场景，如数据处理、性能优化等，因此熟练掌握该算法是非常必要的。
来源：JavaScript中文网 ，转载请注明来源 本文地址：https://www.javascriptcn.com/post/65a4ffe0add4f0e0ffd627ea