欢迎光临
我的个人博客网站

第十三章 搜索算法


二分搜索

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

  • 左指针:指向数组的起始位置,或者你认为的起始搜索的部分
  • 右指针:指向数组的终止位置,或者你认为的终止搜索部分
  • 终止条件:当左指针大于或者等于右指针的时候就结束了
  • 找这两个指针的中间的数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) 
赞(0) 打赏
未经允许不得转载:张拓的天空 » 第十三章 搜索算法
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏