js之二分查找

二分查找基本思路描述

采用二分查找之前，数据应该是排好序的。

主要思路是：设查找的数组区间为array[s,e]

(1)确定区间的中间位置

(2)将要查找的值x与数组中间位置的值作比较array[m]，查找成功则返回此位置；否则重复1、2步，继续确定新的查找位置，继续二分查找。

区域确定过程：这里假设array是按照从小到大的顺序排列的

array[m]>T由数组的有序性可知array[m,…..,e]都大于T;

故新的区间为array[s,…….m-1],

重复上述步骤，每一次查找与中间值进行比较，判断是否成功，不成功则当前查找区间缩小一半，循环查找，即可。

时间复杂度为O（log2 n）；

let arr1=[0,1,2,4,5,6,,7,8];
let arr2=[88,77,66,55,44,33,22,11];

BinarySearch(arr1,2);
BinarySearch(arr2,77);

function BinarySearch(arr,target){
    let s=0;
    let e=arr.length-1;
    let m=Math.floor((s+e)/2);
    let sortTag=arr[s]<=arr[e];  //确定排序的顺序是升序还是降序
    
    while(s<e && arr[m] !==target){
    if(arr[m] >target){
        sortTag && (e=m-1); //
        !sortTag && (s=m+1);
    }
    
    else{
        !sortTag && (e=m-1);
        sortTag && (s=m+1);
    }
    m=Math.floor((s+e)/2);
}

   if(arr[m] == target){
       console.log('找到了，位于%s',m);
       return m;
   }else{
       console.log('没找到');
       return -1;
   }
   

}

这里使用了&& 的短路原理：

1、只要 && 前面是false,无论 && 后面是true还是false,结果都将返回 && 前面的值

2、只要 && 前面是true，无论 && 后面是true还是false,结果都将返回 && 后面的值。

例如：

alert(0 && 'a');

结果返回0， && 前面 0 是false,后面 a是true,所以直接分返回前面的值