二分查找：
前提：
数组并且有序
描述：
①优先与数组的中间元素比较，如果等于中间值，则直接返回元素的牵引值
②如果查找值小于中间值，则在左边的元素重复步骤①
③如果查找值大于中间值，则在邮编的元素重复步骤①
④否则，查找失败，返回-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;
}
