本文介绍JavaScript中二分查找的实现。首先阐述有序数组下的递归与迭代写法，随后探讨无序数组通过快速排序预处理后执行二分查找的方案，并分析其时间复杂度，指出直接遍历在某些场景下可能更高效。
有序数组的二分查找逻辑
二分查找算法的应用前提是数据必须为数组且保持有序状态。其核心逻辑是：每次比较时，先取数组的中间元素与目标值进行比对。若两者相等，则直接返回该元素的索引；若不相等，则根据大小关系舍弃一半数据，继续在剩余区间内执行查找操作。
/**
* 二分查找，递归实现。
* @param target
* @param arr
* @param start
* @param end
* @returns {*}
*/
function binarySearch(target,arr,start,end) {
var start = start || 0;
var end = end || arr.length-1;
var mid = parseInt(start+(end-start)/2);
if(target==arr[mid]){
return mid;
}else if(target>arr[mid]){
return binarySearch(target,arr,mid+1,end);
}else{
return binarySearch(target,arr,start,mid-1);
}
return -1;
}
/**
* 有序的二分查找，返回-1或存在的数组下标。不使用递归实现。
* @param target
* @param arr
* @returns {*}
*/
function binarySearch(target,arr) {
var start = 0;
var end = arr.length-1;
while (start<=end){
var mid = parseInt(start+(end-start)/2);
if(target==arr[mid]){
return mid;
}else if(target>arr[mid]){
start = mid+1;
}else{
end = mid-1;
}
}
return -1;
}在明确了有序数组的处理方式后，进一步思考无序数组是否也能使用二分查找。一种思路是先对无序数组进行快速排序分组，待数据有序后再执行二分查找。具体实现代码如下：
无序数组的快速排序预处理方案
/**
* 无序的二分查找。返回true/false
* @param target
* @param arr
* @returns {boolean}
*/
function binarySearch(target,arr) {
while (arr.length>0){
//使用快速排序。以mid为中心划分大小，左边小，右边大。
var left = [];
var right = [];
//选择第一个元素作为基准元素(基准元素可以为任意一个元素)
var pivot = arr[0];
//由于取了第一个元素，所以从第二个元素开始循环
for(var i=1;i<arr.length;i++){
var item = arr[i];
//大于基准的放右边，小于基准的放左边
item>pivot ? right.push(item) : left.push(item);
}
//得到经过排序的新数组
if(target==pivot){
return true;
}else if(target>pivot){
arr = right;
}else{
arr = left;
}
}
return false;
}算法复杂度对比分析
基于快速排序预处理后的无序二分查找方案，经过对时间复杂度的仔细评估，发现该算法的整体效率并不理想。相比之下，直接使用单次 for 循环遍历数组进行查找，在实际运行中可能更加快速高效。
以上即为关于JavaScript实现二分查找的相关实例代码与原理分析，希望能对读者有所帮助。如有任何疑问，欢迎留言交流，小编将及时回复。同时感谢大家对该网站的支持！