二分搜索

二分搜索是应用在已排序的数组中的搜索算法，其在搜索算法中的高效体现在其一次排除元数据的一半元素【也正因为要排除一半的元素，所以这个算法是在排序的数组中搜索】

• 左指针：指向数组的起始位置，或者你认为的起始搜索的部分
• 右指针：指向数组的终止位置，或者你认为的终止搜索部分
• 终止条件：当左指针大于或者等于右指针的时候就结束了
• 找这两个指针的中间的数middle，与目标target比较
  • middle > target：说明目标在其左侧，那么就将右指针移动到middle - 1位置（注意，这里middle已经比较过了）
  • middle < target：说明目标在其右侧，那么就将左指针移动到middle + 1位置（注意，这里middle也已经比较过了）
  • middler === target：说明这个就是目标，那么就返回位置
  • 最后没找到就返回-1

function defaultCompareFunction<T>(a: T, b: T){   if(a === b){     return Compare.EQUAL   }   return a > b ? Compare.GREATER : Compare.LESS; }  export enum Compare {   LESS =  -1,   EQUAL = 0,   GREATER = 1 }    function binarySearch<T>(arr:Array<T>, target: T , compareFn: Function = defaultCompareFunction){   let left = 0, // 左指针       right = arr.length - 1; // 右指针           // 循环结束条件   while(left <= right){      // 中间数     let middle = Math.floor((left + right) / 2);     if(compareFn(arr[middle], target) === Compare.EQUAL){       // 如果相等的话       return middle;     } else if(compareFn(arr[middle], target) === Compare.LESS) {         left = middle + 1;     } else {         right = middle - 1;     }   }    return -1; }  let index = binarySearch([0,1,2,3,4,5,6,7,8,9,10,12,45], 8); console.log(index)