二分查找(Binary Search)是一种在有序数组中查找目标元素的查找算法。它的基本思路是:在数组的中间元素开始,如果该元素等于目标元素,则查找成功;如果该元素大于目标元素,则在左半部分继续查找;如果该元素小于目标元素,则在右半部分继续查找。这样一直重复这个过程,直到查找成功或者查找失败。
基本步骤:
设置两个指针,left 和 right,分别指向数组的第一个元素和最后一个元素。
计算中间索引,mid = (left + right) / 2。
如果该索引上的元素等于目标元素,则查找成功,返回该索引。
如果该索引上的元素大于目标元素,则说明目标元素在左半部分,将 right 指针移动到 mid-1。
如果该索引上的元素小于目标元素,则说明目标元素在右半部分,将 left 指针移动到 mid+1。
重复步骤2-5,直到查找成功或者 left > right。
如果查找失败,则返回 -1。
二分查找的时间复杂度是 O(log n),比顺序查找和线性查找的时间复杂度更优秀。但是,需要注意的是,二分查找只能用于有序数组。
JavaScript 实现二分查找可以使用递归或迭代两种方法。
这是一个使用递归实现二分查找的示例代码:
function binarySearch(arr, target, left = 0, right = arr.length - 1) { if (left > right) return -1; const mid = Math.floor((left + right) / 2); if (arr[mid] === target) return mid; if (arr[mid] > target) { return binarySearch(arr, target, left, mid - 1); } else { return binarySearch(arr, target, mid + 1, right); }}
这是一个使用迭代实现二分查找的示例代码:
function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while (left target) { right = mid - 1; } else { left = mid + 1; } } return -1;}
在上面的代码中,我们可以看到,递归和迭代两种方法都是基于同样的思想,不断地将查找范围缩小,直到找到目标元素或者缩小到不可能找到目标元素的范围。
两种方法的区别在于,递归方法是使用函数调用栈来保存状态,而迭代方法是使用循环和变量来保存状态。对于大部分情况来说,迭代方法更加高效,因为它避免了函数调用栈的开销。
两种方法都需要注意的是数组是有序的,且需要先确定好左右边界。
这里的代码只是一个简单的二分查找示例,在实际使用中,还需要根据具体需求进行调整和优化。
作者:yuzhihui
出处:http://www.cnblogs.com/yuzhihui/声明:欢迎任何形式的转载,但请务必注明出处!!!