二分查找

二分查找：

前提：

数组并且有序

描述：

①优先与数组的中间元素比较，如果等于中间值，则直接返回元素的牵引值
②如果查找值小于中间值，则在左边的元素重复步骤①
③如果查找值大于中间值，则在邮编的元素重复步骤①
④否则，查找失败，返回-1

//二分查找：递归实现
//数组有序
var binarySearch =  function(target, arr, start=0, end=arr.length-1){
    var start = start;
    var end = end;
    if( start > end){
         return -1
    }
    var mid = parseInt(start+(end-start)/2);

    if(target == arr[mid] ){
        return mid;
    }else if (target < arr[mid]){
        return binarySearch(target, arr, start, mid -1)
    }else {
        return binarySearch(target, arr, mid + 1, end)
    }

}

在数组有序的情况下，自然可以使用以上方法，但是在数组无序的情况下呢？马上就想到先试用快排分组，完成分组后再进行二分查找 show code

//二分查找
//无序数组，先快排，后二分
function binarySearch(target,arr) {
    while (arr.length>0){
        //使用快速排序。以mid为中心划分大小，左边小，右边大。
        var left    = [];
        var right   = [];
        //选择第一个元素作为基准元素(基准元素可以为任意一个元素)
        var pivot   = arr[0];
        //由于取了第一个元素，所以从第二个元素开始循环
        for(var i=1;i<arr.length;i++){
            var item = arr[i];
            //大于基准的放右边，小于基准的放左边
            item>pivot ? right.push(item) : left.push(item);
        }

        //得到经过排序的新数组
        if(target==pivot){
            return true;
        }else if(target>pivot){
            arr     = right;
        }else{
            arr     = left;
        }
    }
    return false;
}