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