JaveScript用二分法与普通遍历(冒泡)

二分法查找

　　概念:

　　　　从有序的数列中,折半查找.

　　思路:

　　　　-->　　找到数组中最中间的元素,将其作为基准

　　　　-->　　从0开始判断数组中的元素,与基准进行比较

　　　　-->　　比基准小的元素,存入左边,

　　　　　　　　比基准打得元素,存入右边

　　　　　　　　依次递归,得出结果

二分法查找函数

 1  function getNum(target, Arr){    
 2         var middle = Math.floor(Arr.length / 2) ,res;
 3         var last = Arr.length;
 4         var temp;
 5         function getRes(target,Arr){
 6             count++;
 7             if (target>Arr[middle]){
 8                 temp=middle;
 9                 middle= Math.floor(middle+Math.abs(last-middle)/2);
10                 last=temp;
11             }else if(target < Arr[middle]){
12                 temp=middle;
13                 middle = Math.floor(middle-Math.abs(last - middle) / 2)  ;  
14                 last=temp;            
15             }else{
16                 res = middle;
17                 return;
18             }
19             if(last==middle){  
20                 Arr[middle]!=target;          
21                 res = "不存在";
22                 return;
23             }
24             return getRes(target,Arr);
25         };
26         getRes(target, Arr);
27         return res;
28     }

普通遍历查找函数

1 function getNum2(target, arr) {
2         for (var i = 0; i < arr.length; i++) {
3             count2++;
4             if (target == arr[i]) {
5                 return i;
6             }
7         }
8         return "不存在";
9     }

生成随机数组

 1  (function(){
 2         var arr = [];
 3         for (var i = 0; i < 50000; i++) {
 4             var flag = true;
 5             var ele = Math.floor(Math.random() * 100000);
 6             for (var j = 0; j < arr.length; j++) {
 7                 if (arr[j] == ele) {
 8                     flag = false;
 9                     break;
10                 }
11             }
12             flag && arr.push(ele);
13         }
14         for (var i = 0; i < arr.length; i++) {
15             for (var j = 0; j < arr.length - i; j++) {
16                 var temp;
17                 if (arr[j] > arr[j + 1]) {
18                     temp = arr[j];
19                     arr[j] = arr[j + 1];
20                     arr[j + 1] = temp;
21                 }
22             }
23         }
24         window.arr=arr;
25         console.log(arr);//数组生成完毕，打印结果;
26     })()

二分法查找

        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("普通遍历耗时");

将二分法与普通遍历封装为函数

 1  function run(x){
 2             count=count2=0;
 3             console.log("二分法查找------------------------");
 4             console.time("二分法耗时");
 5             console.log("结果" +getNum(x, arr));
 6             console.log("查找次数为："+count);
 7             console.timeEnd("二分法耗时");
 8             console.log("普通查找------------------------");
 9             function getNum2(target, arr) {
10                 for (var i = 0; i < arr.length; i++) {
11                     count2++;
12                     if (target == arr[i]) {
13                         return i;
14                     }
15                 }
16                 return "不存在";
17             }
18             var count2 = 0;
19             console.time("普通遍历耗时");
20             console.log("结果"+getNum2(x, arr));
21             console.log("查找次数为："+count2);
22             console.timeEnd("普通遍历耗时");
23         };

直接输入即可验证结果