算法-二分查找

二分查找就是每次都找中间数，然后跟要查找的数对比。

比如有这样一个数组：

var s = [1,2,3,4,5,6,7,8,9,10,104,234]; （排过序的）

你要从中间找到104的下标，怎么办？

我们写一个函数：

---

function BinarySearch(s,x){   

 //s为待查找数组，x为要查找的数

       var a = 0;

       var b = s.length-1;

       while(a<=b){  只要最小数不大于最大数，就一直执行（好像是废话）

                var middle = parseInt((a+b)/2);   //取数组中间下标

                if (x == s[middle]) {

                       return middle;  //找到了，返回结果

                }else if(x < s[middle]){

                      b = middle-1;     //没找到，将中间值作为最大值，继续执行

               }else{

                      a = middle + 1;   //没找到，将中间值作为最小值，继续执行

              }

      }

      return -1;  //数组里没有这个数，返回-1；

}

---

我们要找到104在数组s里所对应的下标，就只需要调用函数

var  res = BinarySearch(s,104);

---

学习了二分法，来个实例：还是刚刚那个数组：

var s = [1,2,3,4,5,6,7,8,9,10,104,234];

要从里面找到2个数，要求他们的相加等于110，怎么做？

先说思想，二分法是找一个数，题目要求是找二个数，怎么办？我们要把问题转化到找一个数上，遍历数组s，每次遍历的时候得到其中一个数s[i],然后去找另外一个数，我们要找相加等于110的数，那另外一个数其实就等于110-s[i]，说到这里是不是已经明白了？

没明白不要紧，贴代码，请看下面这个函数：

---

function searchTwoNum(s,x){ //传数组s 和 两个数之和x

    var dic;

    for(var i = 0; i < s.length;i++){

        var a = s[i];   //假设它是其中一个数

        var b = x - s[i];  //假设a的假设成立，那b就是另一个数

        var n = BinarySearch(s,b); //判断是不是有b，有的话就说明a的假设成立了

        if (n != -1) { //上面说了n==-1的时候实际上就是没找到，所以不等于-1时就找到了

            dic = {i:i,n:n,a:a,b:b};

            break; //找到了就不找了，跳出去

        }

    }

    return dic;

}

---

调用该函数，就可以找到要找的数：

var dic = searchTwoNum(s,110);

console.log(dic);