JavaScript实现二分查找（搜索）算法（非递归实现）

Javascript实现前端经典算法二分查找&＃xff0c;面试常考哟~

一、二分查找算法分析

用二分查找算法查找目标值在数组中对应的下标
1、二分搜索算法的前提是一个有序数组&＃xff0c;所以编码实现的时候&＃xff0c;先对它排了个序
2、二分查找就是
&＃xff08;1&＃xff09;劈成两半&＃xff0c;最左边一个指针low&＃xff0c;最右边一个指针high&＃xff0c;最中间一个指针mid
&＃xff08;2&＃xff09;如果查找的目标值小于中间mid对应的值&＃xff0c;说明目标值在左边&＃xff0c;那就缩小范围&＃xff0c;把high设置成mid-1
&＃xff08;3&＃xff09;如果查找的目标值大于中间mid对应的值&＃xff0c;说明目标值在右边&＃xff0c;那就缩小范围&＃xff0c;把low设置成mid&＃43;1
&＃xff08;4&＃xff09;如果查找的目标值就等于中间mid对应的值&＃xff0c;那还有啥好说的&＃xff0c;直接返回mid
上图~
又到了我的拙劣的画图环节~

二、编码实现

细节写在代码的注释里了

Array.prototype.binarySort &＃61; function(target) {// 随便用什么算法排&＃xff0c;但是二分查找的前提是有序数组哦this.quickSort();let low &＃61; 0;let high &＃61; this.length - 1;while(low <&＃61; high) {const mid &＃61; Math.floor((low &＃43; high) /2);const midItem &＃61; this[mid];// 如果查找的目标值小于中间的点if(target < midItem ) {// 说明目标值在左半边&＃xff0c;那high指针就是mid的前一位high &＃61; mid - 1;} else if(target > midItem) {// 如果目标值在右半边&＃xff0c;那low指针就是mid的后面一位low &＃61; mid &＃43; 1;} else {// 目标值就是正中间return mid;}}// 没找到return -1;
}const arr &＃61; [1, 5, 9, 3, 18, 6, 2, 7]
console.log(arr.binarySort(9));

这里用了一下快速排序算法&＃xff0c;快速排序算法思路和实现可见这篇博客
Javascript实现快速排序算法

Array.prototype.quickSort &＃61; function() {const rec &＃61; (arr) &＃61;> {if(arr.length <&＃61; 1) return arr;const base &＃61; arr[0];const left &＃61; [];const right &＃61; [];for(let i &＃61; 1; i < arr.length; i &＃43;&＃61; 1) {if(arr[i] < base) {left.push(arr[i]);} else {right.push(arr[i]);}}return [...rec(left), base, ...rec(right)];}const res &＃61; rec(this);res.forEach((item, key) &＃61;> {this[key] &＃61; item;});
}


三、时间复杂度

前面博客说过对半劈递归的是O(logn)&＃xff0c;这种对半劈一层循环的也是O(logn)

写完啦~~~~