一稚晚、什么是二分查找崇堵？

??????二分查找針對的是一個(gè)數(shù)據(jù)集合，每次通過跟元素對比客燕，將待查找的區(qū)間縮小為之前的一半鸳劳，直到找到要查找的元素，或者區(qū)間縮小為0也搓。
??????二分查找是一種非常簡單易懂的快速查找算法赏廓，生活中到處可見。比如說傍妒，我們現(xiàn)在來做一個(gè)猜字游戲幔摸。我隨機(jī)寫一個(gè) 0 到 99 之間的數(shù)字，然后你來猜我寫的是什么颤练。猜的過程中既忆，你每猜一次，我就會(huì)告訴你猜的大了還是小了嗦玖，直到猜中為止患雇。你來想想，如何快速猜中我寫的數(shù)字呢踏揣？
??????假設(shè)我寫的數(shù)字是 23庆亡，你可以按照下面的步驟來試一試。（如果猜測范圍的數(shù)字有偶數(shù)個(gè)捞稿，中間數(shù)有兩個(gè)又谋，就選擇較小的那個(gè)。）7 次就猜出來了娱局，是不是很快彰亥？這個(gè)例子用的就是二分思想，按照這個(gè)思想衰齐，即便我讓你猜的是 0 到 999 的數(shù)字任斋，最多也只要 10 次就能猜中。不信的話耻涛，你可以試一試废酷。

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

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

??????假設(shè)數(shù)據(jù)大小是n佩谷，每次查找后數(shù)據(jù)都會(huì)縮小為原來的一半，最壞的情況下监嗜，直到查找區(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)過k次區(qū)間縮小操作夯膀，時(shí)間復(fù)雜度就是O(k)。通過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ù)量級辜荠，即便n非常大，對應(yīng)的logn也很小抓狭。比如n等于2的32次方伯病，也就是42億，而logn才32否过。
③由此可見午笛，O(logn)有時(shí)就是比O(1000)，O(10000)快很多苗桂。

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

最簡單的情況就是中不存在煤伟，我們在其中用二分查找值等于給定值的數(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)算來說考婴，計(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)用場景的局限性）

1.二分查找依賴的是順序表結(jié)構(gòu)，即數(shù)組崇棠。
2.二分查找針對的是有序數(shù)據(jù)咽袜，因此只能用在插入、刪除操作不頻繁枕稀，一次排序多次查找的場景中询刹。
3.數(shù)據(jù)量太小不適合二分查找谜嫉，與直接遍歷相比效率提升不明顯。但有一個(gè)例外凹联，就是數(shù)據(jù)之間的比較操作非常費(fèi)時(shí)沐兰，比如數(shù)組中存儲(chǔ)的都是長度超過300的字符串，那這是還是盡量減少比較操作使用二分查找吧蔽挠。
4.數(shù)據(jù)量太大也不是適合用二分查找住闯，因?yàn)閿?shù)組需要連續(xù)的空間，若數(shù)據(jù)量太大澳淑，往往找不到存儲(chǔ)如此大規(guī)模數(shù)據(jù)的連續(xù)內(nèi)存空間比原。
五、思考
1.如何在1000萬個(gè)整數(shù)中快速查找某個(gè)整數(shù)杠巡？
①1000萬個(gè)整數(shù)占用存儲(chǔ)空間為40MB量窘，占用空間不大，所以可以全部加載到內(nèi)存中進(jìn)行處理忽孽；
②用一個(gè)1000萬個(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位？