1-二分查找.md

二分查找

定义

在一个有序的元素列表中，查找一个元素从中间开始

生活中的案例

比如，我们查找一个以 'k' 开头的通讯录，我们会重中间翻阅 ，亦或者给定一个数 1~100, 我们猜数游戏

需要掌握的知识点

• 对数 : 幂运算的逆运算
• 10² = 100 (幂运算)
• log₁₀ 100 = 2 （对数运算）

特点

• 二分查找，最大查找次数为 log₂n
• 适用于有序的数组，因为通过筛查可确切知道 查找数在前还是在后，这就要求我们的数组 是有序的
• 比如：长度 为8 的 [1,2,3,4,5,6,7,8] 有序元素 二分查找，最大查找次数为 log₂8 = 3,最多3次即可推算出想猜测的数

javaScript 实现

/**
 * 二分查找
 * */

function dichotomySearch (list,item){
   let start = 0
   let end = list.length - 1
 
   while(start <= end){
    let mid = Math.floor((start + end) / 2) // 中节点位置 为 (start+end)/2 向下取整
    const guess = list[mid]
    if(guess > item){ // 如果猜测的数 大于当前数, 当前数 在猜测数前面
        end = mid - 1  // 开始节点 从 中位置加1 开始
    }else if(guess < item ){ // 猜测数小于 当前数，当前数 在 猜测数后面
        start = mid + 1
    }else{
       return mid
    }
       
   }
    return -1;
}