数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 JavaScript 进行二分查找算法在数组中搜索
在 JavaScript 编程领域，能够使用二分查找算法有效地搜索数组具有极其重要的意义。这种算法技术通常被认为是一种优雅而强大的解决方案，它为开发人员提供了一种高性能的方法来在已排序的数组中定位所需元素。掌握使用 JavaScript 进行二分查找不仅展示了个人在算法问题解决方面的熟练程度，还使开发人员能够优化其应用程序中的搜索操作。在本文中，我们将深入探讨在 JavaScript 中实现二分查找的细节，探索其分步过程，并揭示这种强大算法技术领域中很少使用的词汇。
问题陈述
手头的问题涉及在已排序的数组中搜索目标元素，而传统的线性搜索方法由于其时间复杂度，对于较大的数组而言效率低下。
示例输入 -
Array: [2, 5, 8, 12, 16, 23, 38, 42, 57, 69] Target Element: 23
示例输出 -
The target element 23 was found at index 5.
方法
在本文中，我们将看到多种在 JavaScript 中解决上述问题陈述的方法 -
迭代二分查找
递归二分查找
数组方法
方法 1：迭代二分查找
在迭代二分查找中，将 low 和 high 初始化为最低和最高索引。进入一个 while 循环，直到 low 小于或等于 high。计算 mid 为 low 和 high 的平均值。检查 mid 处的数值是否与目标匹配。如果匹配，则返回 mid，表示匹配成功。如果 mid 处的数值小于目标，则将 low 更新为 mid + 1 以在右半部分搜索。如果 mid 处的数值大于目标，则将 high 更新为 mid - 1 以在左半部分搜索。如果 while 循环完成而未找到目标，则返回 -1 以指示未找到。
示例
binarySearch 函数接受一个数组和一个目标值。它将 low 和 high 初始化为搜索空间的最低和最高索引。使用 while 循环，它计算 mid 索引并检查数值是否与目标匹配。如果匹配，则返回 mid 索引。如果数值小于目标，则更新 low；如果大于，则更新 high。如果循环结束而未找到目标，则返回 -1。
function binarySearch(array, target) {
let low = 0;
let high = array.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (array[mid] === target) {
return mid; // Target found at index mid
} else if (array[mid] < target) {
low = mid + 1; // Discard the left half
} else {
high = mid - 1; // Discard the right half
}
}
return -1; // Target not found
}
const array = [2, 5, 8, 12, 16, 23, 38, 42, 57, 69];
const target = 23;
console.log(`Target found at index: ${binarySearch(array, target)}`);
输出
以下是控制台输出 -
Target found at index: 5
方法 2：递归二分查找
在递归二分查找中，定义了一个名为 binarySearch 的函数，其参数为数组、目标值、low 和 high 索引。它检查 low 是否大于 high，如果为真则返回 -1。mid 索引计算为 low 和 high 的平均值。如果 mid 索引处的数值与目标匹配，则返回 mid 索引。如果 mid 索引处的数值小于目标，则递归调用 binarySearch 函数，搜索空间为右半部分。如果 mid 索引处的数值大于目标，则递归调用 binarySearch 函数，搜索空间为左半部分。此过程持续进行，直到找到目标或搜索空间用尽，如果未找到目标则返回 -1。
示例
binarySearch 函数是一个递归实现，它在数组中搜索目标值。它通过比较 low 和 high 索引来检查搜索空间是否为空。如果是，则返回 -1。否则，它计算 mid 索引，检查 mid 处的数值是否与目标匹配，如果匹配则返回 mid。如果 mid 处的数值小于目标，则递归调用自身，搜索空间为右半部分。如果 mid 处的数值大于，则递归调用自身，搜索空间为左半部分。此过程持续进行，直到找到目标或确定目标不存在。
function binarySearch(array, target, low = 0, high = array.length - 1) {
if (low > high) {
return -1; // Target not found
}
let mid = Math.floor((low + high) / 2);
if (array[mid] === target) {
return mid; // Target found at index mid
} else if (array[mid] < target) {
return binarySearch(array, target, mid + 1, high); // Search the right half
} else {
return binarySearch(array, target, low, mid - 1); // Search the left half
}
}
const array = [2, 5, 8, 12, 16, 23, 38, 42, 57, 69];
const target = 23;
console.log(`Target found at index: ${binarySearch(array, target)}`);
输出
以下是控制台输出 -
Target found at index: 5
方法 3：数组方法
binarySearch 函数接受一个数组和一个目标值作为参数。它使用 indexOf() 方法来查找目标值，并将结果赋给 index 变量。通过检查 indexOf() 方法是否产生一个与 -1 不同的值，它确定是否存在匹配。如果检测到匹配，则函数输出索引。但是，如果 indexOf() 方法返回 -1，表示目标不存在，则函数返回 -1 以传达此状态。
示例
binarySearch 函数接受一个数组和一个目标值作为参数，并使用 indexOf() 方法来确定目标在数组中的索引。它将结果赋给 index 变量，如果找到目标则返回索引。或者，如果未找到目标，则返回 -1。
function binarySearch(array, target) {
const index = array.indexOf(target);
return index !== -1 ? index : -1;
}
const array = [2, 5, 8, 12, 16, 23, 38, 42, 57, 69];
const target = 23;
console.log(`Target found at index: ${binarySearch(array, target)}`);
输出
以下是控制台输出 -
Target found at index: 5
结论
总之，使用 JavaScript 在数组中搜索时使用二分查找算法可能是一种非常有效的方法。通过利用算法的对数时间复杂度，我们可以加快搜索过程并优化性能，尤其是在处理较大的数组时。明智地实施二分查找使开发人员能够有效地定位所需元素，从而改善用户体验并增强应用程序功能。因此，将此方法集成到 JavaScript 代码中对于处理大量数据集和实现简化的搜索操作可能非常宝贵。
447 次查看
