JavaScript 二分查找

时画

二分查找（Binary Search）是一种在有序数组中查找目标元素的查找算法。它的基本思路是：在数组的中间元素开始，如果该元素等于目标元素，则查找成功；如果该元素大于目标元素，则在左半部分继续查找；如果该元素小于目标元素，则在右半部分继续查找。这样一直重复这个过程，直到查找成功或者查找失败。
基本步骤：

• 设置两个指针，left 和 right，分别指向数组的第一个元素和最后一个元素。
  
• 计算中间索引，mid = (left + right) / 2。
  
• 如果该索引上的元素等于目标元素，则查找成功，返回该索引。
  
• 如果该索引上的元素大于目标元素，则说明目标元素在左半部分，将 right 指针移动到 mid-1。
  
• 如果该索引上的元素小于目标元素，则说明目标元素在右半部分，将 left 指针移动到 mid+1。
  
• 重复步骤2-5，直到查找成功或者 left > right。
  
• 如果查找失败，则返回 -1。
  

二分查找的时间复杂度是 O(log n)，比顺序查找和线性查找的时间复杂度更优秀。但是，需要注意的是，二分查找只能用于有序数组。
JavaScript 实现二分查找可以使用递归或迭代两种方法。
这是一个使用递归实现二分查找的示例代码：

1. function binarySearch(arr, target, left = 0, right = arr.length - 1) {
2.   if (left > right) return -1;
4.   const mid = Math.floor((left + right) / 2);
5.   if (arr[mid] === target) return mid;
6.   if (arr[mid] > target) {
7.     return binarySearch(arr, target, left, mid - 1);
8.   } else {
9.     return binarySearch(arr, target, mid + 1, right);
10.   }
11. }

复制代码

这是一个使用迭代实现二分查找的示例代码：

1. function binarySearch(arr, target) {
2.   let left = 0;
3.   let right = arr.length - 1;
4.   while (left <= right) {
5.     const mid = Math.floor((left + right) / 2);
6.     if (arr[mid] === target) return mid;
7.     if (arr[mid] > target) {
8.       right = mid - 1;
9.     } else {
10.       left = mid + 1;
11.     }
12.   }
13.   return -1;
14. }

复制代码

在上面的代码中，我们可以看到，递归和迭代两种方法都是基于同样的思想，不断地将查找范围缩小，直到找到目标元素或者缩小到不可能找到目标元素的范围。
两种方法的区别在于，递归方法是使用函数调用栈来保存状态，而迭代方法是使用循环和变量来保存状态。对于大部分情况来说，迭代方法更加高效，因为它避免了函数调用栈的开销。
两种方法都需要注意的是数组是有序的，且需要先确定好左右边界。
这里的代码只是一个简单的二分查找示例，在实际使用中，还需要根据具体需求进行调整和优化。
 

来源:https://www.cnblogs.com/yuzhihui/p/17048874.html
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！