二分法 查找
概念:
从有序的数列中,折半查找.
思路:
--> 找到数组中最中间的元素,将其作为基准
--> 从0开始判断数组中的元素,与基准进行比较
--> 比基准小的元素,存入左边,
比基准打得元素,存入右边
依次递归,得出结果
二分法查找函数
function getNum(target, Arr){
var middle = Math.floor(Arr.length / 2) ,res;
var last = Arr.length;
var temp;
function getRes(target,Arr){
count++;
if (target>Arr[middle]){
temp=middle;
middle= Math.floor(middle+Math.abs(last-middle)/2);
last=temp;
}else if(target < Arr[middle]){
temp=middle;
middle = Math.floor(middle-Math.abs(last - middle) / 2) ;
last=temp;
}else{
res = middle;
return;
}
if(last==middle){
Arr[middle]!=target;
res = "不存在";
return;
}
return getRes(target,Arr);
};
getRes(target, Arr);
return res;
}普通遍历查找函数
function getNum2(target, arr) {
for (var i = 0; i < arr.length; i++) {
count2++;
if (target == arr[i]) {
return i;
}
}
return "不存在";
}生成随机数组
(function(){
var arr = [];
for (var i = 0; i < 50000; i++) {
var flag = true;
var ele = Math.floor(Math.random() * 100000);
for (var j = 0; j < arr.length; j++) {
if (arr[j] == ele) {
flag = false;
break;
}
}
flag && arr.push(ele);
}
for (var i = 0; i < arr.length; i++) {
for (var j = 0; j < arr.length - i; j++) {
var temp;
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
window.arr=arr;
console.log(arr);//数组生成完毕，打印结果;
})()二分法查找
var count=0;
console.log("二分法查找------------------------");
console.time("二分法耗时");
console.log("结果" +getNum(31322, arr));
console.log("查找次数为："+count);
console.timeEnd("二分法耗时");
console.log("普通查找------------------------");
普通遍历
var count2=0;
console.time("普通遍历耗时");
console.log("结果" +getNum2(31322, arr));
console.log("查找次数为："+count2);
console.timeEnd("普通遍历耗时");
将二分法与普通遍历封装为函数
function run(x){
count=count2=0;
console.log("二分法查找------------------------");
console.time("二分法耗时");
console.log("结果" +getNum(x, arr));
console.log("查找次数为："+count);
console.timeEnd("二分法耗时");
console.log("普通查找------------------------");
function getNum2(target, arr) {
for (var i = 0; i < arr.length; i++) {
count2++;
if (target == arr[i]) {
return i;
}
}
return "不存在";
}
var count2 = 0;
console.time("普通遍历耗时");
console.log("结果"+getNum2(x, arr));
console.log("查找次数为："+count2);
console.timeEnd("普通遍历耗时");
};直接输入即可验证结果