二分法算法
如果你要查找的数据是有序的,二分查找算法比顺序查找算法更高效。
算法理解
二分搜索算法的原理和猜数字游戏类似,就是那个有人说“我正想着一个1到100的数字”的游戏。
我们每回应一个数字,那个人就会说这个数字是高了、低了还是对了。
算法描述
①选择中间值;
②如果选择的值是待搜索的值,算法结束并返回;
③如果待搜索值比选中值要小,则返回步骤①并在选中值左边的子数组中寻找。
④如果待搜索值比选中值要大,则返回步骤①并在选中值右边的子数组中寻找。算法实现
function binSearch(arr,data) {
//将传入的数组用快速排序算法排序一下
var arr = qSort(arr);
//将最后一个元素所在的位置设为上边界
var upperBound = arr.length-1;
//将数组的第一个位置设为下边界
var lowerBound = 0;
while(lowerBound <= upperBound) {
//中点
var mid = Math.floor((upperBound + lowerBound)/2);
//如果待查询的值大于中点元素,则将下边界设置为中点元素所在下标加1,
也就是选取数组的右半边(不包括中点元素),然后再在里面查找
if(arr[mid] < data) {
lowerBound = mid+1;
//如果待查询的值小于中点元素,同理如上
}else if(arr[mid] > data) {
upperBound = mid-1;
//否则如果相等,返回
}else {
return mid;
}
}
return -1;
}
var test = [1,2,3,4,5,6];
console.log(binSearch(test,2)); //位置”1”