門(mén)戶網(wǎng)站源碼入駐/站長(zhǎng)之家收錄查詢
?????
?
?二分查找
? ? 題目描述? ??
? ? 題目解析? ??
? ? 暴力解法? ??
我們可以從左往右遍歷一次數(shù)組，如果存在 target 則返回?cái)?shù)組的下標(biāo)，否則返回 -1；
時(shí)間復(fù)雜度 O(N)，因?yàn)闆](méi)有利用數(shù)組有序的特點(diǎn)，每次比較只能舍棄一個(gè)要比較的數(shù)；
? ? 二分查找法? ??
所以我們可以把 [1 , 4 ] 這個(gè)區(qū)間舍棄掉，直接看 [ 5 , 8 ]；僅僅拿 4 和 5 比較一次，就干掉了一大片數(shù)；
? ? 總結(jié)? ??
在一個(gè)數(shù)組中，隨便找一個(gè)數(shù)，拿這個(gè)數(shù)和 target 進(jìn)行比較，并且以拿的這個(gè)數(shù)分成兩個(gè)區(qū)間，比較后舍棄一部分?jǐn)?shù)，然后再?gòu)牧硪粋€(gè)區(qū)間的數(shù)中，找下一個(gè)要和 target 比較的數(shù)；
二分查找算法的本質(zhì)，就是當(dāng)數(shù)組具有“二段性”時(shí)，哪怕這個(gè)數(shù)組是無(wú)序的，只要能在這個(gè)數(shù)組中發(fā)現(xiàn)“二段性”，那么也可以使用二分查找；
? ? “二段性”? ???
當(dāng)我們發(fā)現(xiàn)一個(gè)規(guī)律，然后根據(jù)這個(gè)規(guī)律，選取某一個(gè)點(diǎn)，根據(jù)這個(gè)點(diǎn)，能把數(shù)組分成兩個(gè)區(qū)域，根據(jù)規(guī)律能夠有選擇地舍棄一部分，進(jìn)而在另一個(gè)部分繼續(xù)查找的時(shí)候，此時(shí)，就可以使用二分查找的算法
?
我們要從數(shù)組中找和 target 進(jìn)行比較的數(shù)，不一定是先從 n/2 的位置開(kāi)始找，只要找的這個(gè)數(shù)的點(diǎn)，能把這個(gè)區(qū)間分成兩部分，即滿足二段性，進(jìn)而使用二分查找法；
但是哪怕那么多點(diǎn)可以選擇，但是我們都應(yīng)該先選擇?n/2 的位置的點(diǎn)，因?yàn)樵诟怕蕦W(xué)的數(shù)學(xué)期望中，我們選擇中間的點(diǎn)，時(shí)間復(fù)雜度是最好的；
?
- nums[mid] < target，left = mid+1
- nums[mid] = target，return mid
- nums[mid] > target，right = mid-1
? ? 細(xì)節(jié)問(wèn)題? ??
因?yàn)楫?dāng) left = right 的時(shí)候，也是要繼續(xù)判斷的，所以 left <= right 為循環(huán)判斷條件；
時(shí)間復(fù)雜度，只需要看循環(huán)執(zhí)行多少次：
如何求 x 呢？
int mid = (left? + right) / 2，mid 會(huì)有溢出風(fēng)險(xiǎn)：
如果想不從 n/2 開(kāi)始查找，可以修改，如下面的寫(xiě)法是從 n/3 開(kāi)始查找的：?
?在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置?
? ? 題目解析? ? ?
? ? 發(fā)現(xiàn)二段性? ???
? ? 方法一：利用數(shù)組有序特性，使用簡(jiǎn)單的二分查找法? ??
如果使用簡(jiǎn)單的二分查找，創(chuàng)建左指針和右指針，再找中間值，對(duì)這個(gè)中間值分別進(jìn)行討論；如果對(duì)于一些特點(diǎn)的情況，如下面的這種情況，這個(gè)方法的時(shí)間復(fù)雜度會(huì)非常高；
雖然 mid 指針剛好指向 target，但是不能確定此時(shí)的 mid 指向的是在目標(biāo)連續(xù)區(qū)域的哪一個(gè)位置，從而不好找目標(biāo)區(qū)域的起始位置和終點(diǎn)位置；
所以使用簡(jiǎn)單二分查找的方法，對(duì)于上述情況和類(lèi)似情況，查找的時(shí)間復(fù)雜度會(huì)近似于暴力查找；?
? ? 方法二：在簡(jiǎn)單二分查找方法的基礎(chǔ)上，對(duì)二分策略進(jìn)行優(yōu)化? ??
回到題目的規(guī)律：當(dāng)發(fā)現(xiàn)題目具有二段性，就可以利用二分查找；
因?yàn)椴荒芡瑫r(shí)查找目標(biāo)區(qū)間起始位置和終點(diǎn)位置，所以我們可以先查找起始位置；
利用二段性，我們可以根據(jù)目標(biāo)值起始位置，把數(shù)組區(qū)間分成兩個(gè)部分；
左邊區(qū)域的值都是小于 target，右邊區(qū)域的值都大于等于target，根據(jù) target，在查詢目標(biāo)區(qū)域左端點(diǎn)的時(shí)候，發(fā)現(xiàn)這個(gè)數(shù)組是有二段性，因此可以使用二分查找：
? ? 查找區(qū)間左端點(diǎn)? ???
? ? 以 mid 的值來(lái)決定 left 和 right 的更新方法? ??
我們?cè)O(shè) mid 指向的值為 x，我們要找 >=target 區(qū)間的起始位置，拿 x 的值與 target 討論；
- 1. x < target，此時(shí) mid 落在 < target 的區(qū)域，不可能有最終結(jié)果，所以繼續(xù)往下執(zhí)行：
- 2. x >= target
(不同點(diǎn)，之前簡(jiǎn)單二分查找的方法分三種情況討論，這里只分兩種情況，因?yàn)?x= target 并不是最終的結(jié)果，因?yàn)樽罱K的結(jié)果的左端點(diǎn)和右端點(diǎn))
對(duì)于這種情況，對(duì)應(yīng)的做法：
我們雖然[mid , right] 區(qū)間的情況一定是都大于 target，但是不知道 [left , mid] 區(qū)間的具體情況是都小于 target 還是部分小于 target；所以 right 絕對(duì)不能移動(dòng)到?[left , mid] 這個(gè)不確定的區(qū)間，因?yàn)槿绻?mid 在修改之前就是目標(biāo)區(qū)間的左端點(diǎn)，讓 right = mid -1，[left , right]這個(gè)區(qū)間就沒(méi)有 target 了，所以 right = mid 即可；
? ? 處理細(xì)節(jié)問(wèn)題? ?
? ? 1.循環(huán)條件? ??
對(duì)于執(zhí)行循環(huán)操作（二分查找操作）的第一個(gè)循環(huán)條件，是 left <= right，還是 left < right 呢？
一定是選擇 left< right ，為什么呢？有兩個(gè)原因；
- ? ? ?原因一：因?yàn)?left = right 的情況不需要放到循環(huán)中判斷? ??
我們分三種情況來(lái)討論（ret 為返回的最終結(jié)果）：
- ? ? 1. 數(shù)組中有元素等于 target? ??
前面提到，left 剛開(kāi)始一直處于 < target 的區(qū)間，在 x>=?target 的條件下，right=mid，所以right 一定在 ret 右邊的區(qū)間，threshold 為ret （第一個(gè) target 元素）的前一個(gè)元素；
?
因?yàn)?left 和 right 的調(diào)整方式是 left = mid+1，right = mid，所以 right 一直在>= target 的區(qū)域移動(dòng)，而 left = mid +1，說(shuō)明 left 是一直想要跳出 < target 的區(qū)域的；
所以當(dāng) left 和 right 調(diào)整到最后，循環(huán)結(jié)束，此時(shí) left 一定會(huì)和 right 相等，此時(shí)我們?cè)谘h(huán)結(jié)束后單獨(dú)判斷相遇點(diǎn)和 target 是否相等即可；如果 left = right ，那么兩個(gè)指針指向的位置，一定就是目標(biāo)區(qū)間左端點(diǎn) ret，所以循環(huán)條件只需要判斷?left < right 即可；
- ? ? 2. 數(shù)組中所有元素全都大于 target? ??
如果所有數(shù)組元素都大于 target，那么整個(gè)過(guò)程只有 right 指針在不斷向左邊移動(dòng)，直到 left 和 right 相遇；
哪怕相遇，也沒(méi)有最終結(jié)果，所以這種情況下，我們只需要在left <?right 時(shí)執(zhí)行循環(huán)，循環(huán)退出，left=right；
此時(shí)我們只需要拿當(dāng)前兩個(gè)指針指向的值和 target 比較：相同則回到第一種情況，這個(gè)值就是目標(biāo)區(qū)間的左端點(diǎn)；不相同則返回 [-1,-1]；
- ? ?3. 數(shù)組中所有元素全都小于 target? ??
這種情況和第二種情況同理：
整個(gè)更新過(guò)程都只有 left 在移動(dòng)，循環(huán)退出時(shí)，left = right，只需要判斷當(dāng)前指針的值和 target 是否相等即可，相等則這個(gè)值就是目標(biāo)區(qū)域的起始位置 ret，否則返回 [-1,-1]；
- ? ?原因二：如果在循環(huán)條件中判斷 left = right，會(huì)出現(xiàn)死循環(huán)? ?
?什么時(shí)候會(huì)出現(xiàn)死循環(huán)，就是整個(gè)數(shù)組中有元素等于 target 的時(shí)候：
如果循環(huán)條件是 while(left <= right){ ..... }，此時(shí)left = right ，更新的 mid還是指向 left，right 所在位置，此時(shí)滿足 x <= target 條件，right=mid，所以 right = left，left 和 right 就會(huì)一直停在一個(gè)地方循環(huán)更新結(jié)果，這種情況下就會(huì)出現(xiàn)死循環(huán)；
? ? 2. 求中點(diǎn)操作? ??
求中點(diǎn)操作，也就是在定義 left 和 right 之后，求 mid 的操作；?
- 1. mid = left + ( right - left ) / 2 ;
- 2. mid = left +( right - left +1 ) /2 ;
這兩種求中點(diǎn)的操作，區(qū)別在于數(shù)組元素是偶數(shù)時(shí)，更新 mid 的位置不同；這兩種方法在簡(jiǎn)單二分情況，如第一題的情況都是可以用的，但是這種情況下不能用?mid = left + (right - left +1)/2 求中點(diǎn)；
如果是用第二種方法 mid = left + (right - left +1)/2，此時(shí) mid 的位置：
- 如果上圖條件中，target >?3，那么此時(shí) mid < target ，left = mid+1，程序結(jié)束，此時(shí)是沒(méi)問(wèn)題的；
- 但是，如果 target <=3，那么此時(shí) mid>=target，此時(shí)調(diào)整 right = mid，就又進(jìn)入死循環(huán)了：
所以，在求左端點(diǎn)時(shí)，只能用 mid = left +(right - left )/2 來(lái)求中點(diǎn)；
? ? 查找區(qū)間右端點(diǎn)? ??
根據(jù)查找右端點(diǎn)，依舊可以把整個(gè)區(qū)間分成兩部分，<=target，>target?:
? ?根據(jù) mid 與 target 的關(guān)系決定更新操作? ??
? ? 1. x?<= target? ??
因?yàn)槲覀円ＷC在調(diào)整 left 和 right 的過(guò)程中，右端點(diǎn)一定要在 [left，right] 區(qū)間，所以當(dāng)前這種情況，我們應(yīng)該移動(dòng) left：
? ? 2. x > target? ??
因?yàn)?x > target，所以mid 所在位置一定是在目標(biāo)區(qū)域之外，因此更新 right = mid -1；
? ? 處理細(xì)節(jié)問(wèn)題? ??
? ? 1. 循環(huán)條件? ?
?
? ? 2. 求中點(diǎn)的操作? ??
循環(huán)條件和求左端點(diǎn)相同，不同的是求中點(diǎn)的公式?
- ?1. mid = left + ( right - left ) / 2 ;
- 2. mid = left +( right - left +1 ) /2 ;
這兩種求中點(diǎn)的操作，區(qū)別在于數(shù)組元素是偶數(shù)時(shí)，更新 mid 的位置不同；這兩種方法在簡(jiǎn)單二分情況，如第一題的情況都是可以用的，但是這種情況下不能用?mid = left + (right - left )/2 求中點(diǎn)；
為了接下來(lái)的操作不和求左端點(diǎn)的時(shí)候弄混，要牢記此時(shí)要求的是右端點(diǎn)，接下來(lái)的假設(shè)都是為了能求出右端點(diǎn)：
如果是用第二種方法 mid = left + (right - left )/2，此時(shí) mid 的位置：
- 如果上圖條件中，target <?2，那么此時(shí) mid >?target ，right = mid-1，程序結(jié)束，此時(shí)是沒(méi)問(wèn)題的；
- 但是，如果 target >=3，那么此時(shí) mid>=target，此時(shí)調(diào)整 left?= mid，就又進(jìn)入死循環(huán)了：
?
所以，在求右端點(diǎn)時(shí)，只能用 mid = left +(right - left +1 )/2 來(lái)求中點(diǎn)，在求右端點(diǎn)時(shí)，為什么用這條公式求中點(diǎn)不會(huì)出現(xiàn)死循環(huán)呢？
用?mid = left +(right - left +1 )/2? 來(lái)求中點(diǎn)，此時(shí) mid 在 right 的位置，如果此時(shí)?x >?target，right=mid-1，此時(shí)不滿足 left<right 的條件，會(huì)結(jié)束循環(huán)；如果 x<= target，left = mid :
此時(shí)也不滿足 left<right 的條件，也會(huì)結(jié)束循環(huán)，所以在求右端點(diǎn)的時(shí)候，用?mid = left +(right - left +1)/2? 來(lái)求中點(diǎn)，就不會(huì)出現(xiàn)死循環(huán)；
? ? 編寫(xiě)代碼? ??
? ? 總結(jié)二分模板? ?
?????
?