一、什么是二分查找？

??????二分查找針對(duì)的是一個(gè)數(shù)據(jù)集合，每次通過(guò)跟元素對(duì)比，將待查找的區(qū)間縮小為之前的一半，直到找到要查找的元素，或者區(qū)間縮小為0。
??????二分查找是一種非常簡(jiǎn)單易懂的快速查找算法，生活中到處可見。比如說(shuō)，我們現(xiàn)在來(lái)做一個(gè)猜字游戲。我隨機(jī)寫一個(gè) 0 到 99 之間的數(shù)字，然后你來(lái)猜我寫的是什么。猜的過(guò)程中，你每猜一次，我就會(huì)告訴你猜的大了還是小了，直到猜中為止。你來(lái)想想，如何快速猜中我寫的數(shù)字呢？
??????假設(shè)我寫的數(shù)字是 23，你可以按照下面的步驟來(lái)試一試。（如果猜測(cè)范圍的數(shù)字有偶數(shù)個(gè)，中間數(shù)有兩個(gè)，就選擇較小的那個(gè)。）7 次就猜出來(lái)了，是不是很快？這個(gè)例子用的就是二分思想，按照這個(gè)思想，即便我讓你猜的是 0 到 999 的數(shù)字，最多也只要 10 次就能猜中。不信的話，你可以試一試。

二、時(shí)間復(fù)雜度分析？

1.時(shí)間復(fù)雜度

??????假設(shè)數(shù)據(jù)大小是n，每次查找后數(shù)據(jù)都會(huì)縮小為原來(lái)的一半，最壞的情況下，直到查找區(qū)間被縮小為空，才停止。所以，每次查找的數(shù)據(jù)大小是：n，n/2，n/4，…，n/(2^k)， …，這是一個(gè)等比數(shù)列。當(dāng)n/(2^k) =1時(shí)，k的值就是總共縮小的次數(shù)，也是查找的總次數(shù)。而每次縮小操作只涉及兩個(gè)數(shù)據(jù)的大小比較，所以，經(jīng)過(guò)k次區(qū)間縮小操作，時(shí)間復(fù)雜度就是O(k)。通過(guò)n/(2^k)=1，可求得k=log2n，所以時(shí)間復(fù)雜度是O(logn)。

2.認(rèn)識(shí)O(logn)

①這是一種極其高效的時(shí)間復(fù)雜度，有時(shí)甚至比O(1)的算法還要高效。為什么？
②因?yàn)閘ogn是一個(gè)非?！翱植馈暗臄?shù)量級(jí)，即便n非常大，對(duì)應(yīng)的logn也很小。比如n等于2的32次方，也就是42億，而logn才32。
③由此可見，O(logn)有時(shí)就是比O(1000)，O(10000)快很多。

三、如何實(shí)現(xiàn)二分查找？

最簡(jiǎn)單的情況就是中不存在，我們?cè)谄渲杏枚植檎抑档扔诮o定值的數(shù)據(jù)。

1.循環(huán)實(shí)現(xiàn)

代碼實(shí)現(xiàn)：

function bsearch(arr, value){
    let len = arr.length
    if(len <= 1) retrun

    let low = 0;
    let high = len - 1;

    while(low <= high){
        let mid = Math.floor((low + high) / 2)
        if(arr[mid] == value){
            return mid;
        } else if(arr[mid] < value){
            low = mid + 1;
        } else if(arr[mid] > value){
            high = mid - 1
        }
    }

    return -1;
}

console.log(bsearch([1,2,3,4,5,6,7,8,9,10],10))

注意事項(xiàng)：

①循環(huán)退出條件是：start<=end，而不是start<end。
②mid的取值，使用mid=start + (end - start) / 2，而不用mid=(start + end)/2，因?yàn)槿绻鹲tart和end比較大的話，求和可能會(huì)發(fā)生int類型的值超出最大范圍。為了把性能優(yōu)化到極致，可以將除以2轉(zhuǎn)換成位運(yùn)算，即start + ((end - start) >> 1)，因?yàn)橄啾瘸ㄟ\(yùn)算來(lái)說(shuō)，計(jì)算機(jī)處理位運(yùn)算要快得多。
③start和end的更新：start = mid - 1，end = mid + 1，若直接寫成start = mid，end=mid，就可能會(huì)發(fā)生死循環(huán)。
2.遞歸實(shí)現(xiàn)

function binarySearch(arr, value){
    return bsearch(arr, value, 0, arr.length -1)
}

function bsearch(arr, value, start, end){
    if(start > end) return  -1;
    let mid = Math.floor((end + (end - start)) / 2)
    if(arr[mid] === value){
        return mid;
    } else if(value > arr[mid]){
        start = mid + 1
    } else {
        end = mid - 1
    }
    return bsearch(arr, value, start, end)
}

console.log(binarySearch([1,2,3,4,5,6,7,8,9,10],10))

四、使用條件（應(yīng)用場(chǎng)景的局限性）

1.二分查找依賴的是順序表結(jié)構(gòu)，即數(shù)組。
2.二分查找針對(duì)的是有序數(shù)據(jù)，因此只能用在插入、刪除操作不頻繁，一次排序多次查找的場(chǎng)景中。
3.數(shù)據(jù)量太小不適合二分查找，與直接遍歷相比效率提升不明顯。但有一個(gè)例外，就是數(shù)據(jù)之間的比較操作非常費(fèi)時(shí)，比如數(shù)組中存儲(chǔ)的都是長(zhǎng)度超過(guò)300的字符串，那這是還是盡量減少比較操作使用二分查找吧。
4.數(shù)據(jù)量太大也不是適合用二分查找，因?yàn)閿?shù)組需要連續(xù)的空間，若數(shù)據(jù)量太大，往往找不到存儲(chǔ)如此大規(guī)模數(shù)據(jù)的連續(xù)內(nèi)存空間。
五、思考
1.如何在1000萬(wàn)個(gè)整數(shù)中快速查找某個(gè)整數(shù)？
①1000萬(wàn)個(gè)整數(shù)占用存儲(chǔ)空間為40MB，占用空間不大，所以可以全部加載到內(nèi)存中進(jìn)行處理；
②用一個(gè)1000萬(wàn)個(gè)元素的數(shù)組存儲(chǔ)，然后使用快排進(jìn)行升序排序，時(shí)間復(fù)雜度為O(nlogn)
③在有序數(shù)組中使用二分查找算法進(jìn)行查找，時(shí)間復(fù)雜度為O(logn)
2.如何編程實(shí)現(xiàn)“求一個(gè)數(shù)的平方根”？要求精確到小數(shù)點(diǎn)后6位？