一、什么是二分查找页衙？

二分查找針對(duì)的是一個(gè)有序的數(shù)據(jù)集合摊滔，每次通過跟區(qū)間中間的元素對(duì)比，將待查找的區(qū)間縮小為之前的一半店乐，直到找到要查找的元素惭载，或者區(qū)間縮小為0。

二响巢、時(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ù)量級(jí)贷币，即便n非常大，對(duì)應(yīng)的logn也很小亏狰。比如n等于2的32次方役纹，也就是42億，而logn才32暇唾。
• 由此可見促脉，O(logn)有時(shí)就是比O(1000)，O(10000)快很多策州。

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

1. 循環(huán)實(shí)現(xiàn)
   注意事項(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)

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

1. 二分查找依賴的是順序表結(jié)構(gòu)诀艰，即數(shù)組。
2. 二分查找針對(duì)的是有序數(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. 二分查找的循環(huán)和遞歸實(shí)現(xiàn)
2. 二分查找的注意事項(xiàng)，退出條件等
3. 二分查找的時(shí)間復(fù)雜度分析
4. 假設(shè)我們有 1000 萬個(gè)整數(shù)數(shù)據(jù)外潜，每個(gè)數(shù)據(jù)占 8 個(gè)字節(jié)原环，如何設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和算法，快速判斷某個(gè)整數(shù)是否出現(xiàn)在這 1000 萬數(shù)據(jù)中处窥？ 我們希望這個(gè)功能不要占用太多的內(nèi)存空間嘱吗，最多不要超過 100MB，你會(huì)怎么做呢滔驾？
5. 假設(shè)有 1000 條訂單數(shù)據(jù)柜与，已經(jīng)按照訂單金額從小到大排序，每個(gè)訂單金額都不同嵌灰，并且最小單位是元弄匕。我們現(xiàn)在想知道是否存在金額等于 19 元的訂單。如果存在沽瞭，則返回訂單數(shù)據(jù)迁匠，怎么做？
6. 如何編程實(shí)現(xiàn)“求一個(gè)數(shù)的平方根”驹溃？要求精確到小數(shù)點(diǎn)后 6 位城丧？
7. 我剛才說了，如果數(shù)據(jù)使用鏈表存儲(chǔ)豌鹤，二分查找的時(shí)間復(fù)雜就會(huì)變得很高亡哄，那查找的時(shí)間復(fù)雜度究竟是多少呢？如果你自己推導(dǎo)一下布疙，你就會(huì)深刻地認(rèn)識(shí)到蚊惯，為何我們會(huì)選擇用數(shù)組而不是鏈表來實(shí)現(xiàn)二分查找了。
8. 查找第一個(gè)值等于給定值的元素
9. 查找最后一個(gè)值等于給定值的元素
10. 查找第一個(gè)大于等于給定值的元素
11. 查找最后一個(gè)小于等于給定值的元素
12. 如何快速定位出一個(gè) IP 地址的歸屬地灵临？
13. 如果有序數(shù)組是一個(gè)循環(huán)有序數(shù)組截型，比如 4，5儒溉，6宦焦，1，2，3波闹。針對(duì)這種情況酝豪，如何實(shí)現(xiàn)一個(gè)求“值等于給定值”的二分查找算法呢？(leetcode 33)