天天看點
傳回

二分查找總結一、尋找一個數二、尋找左側邊界的二分搜尋三、尋找右側邊界的二分查找四、總結

作者：labuladong

連結：https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/

最常用的二分查找場景：尋找一個數、尋找左側邊界、尋找右側邊界。而且，我們就是要深入細節，比如不等号是否應該帶等号，mid 是否應該加一等等。分析這些細節的差異以及出現這些差異的原因，保證你能靈活準确地寫出正确的二分查找算法。

另外聲明一下，計算 mid 時需要防止溢出，代碼中 left + (right - left) / 2 就和 (left + right) / 2 的結果相同，但是有效防止了 left 和 right 太大直接相加導緻溢出。

二分查找的基本架構

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

一、尋找一個數 

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 防止溢出

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

1、為什麼 while 循環的條件中是 <=，而不是 <？

答：因為初始化 right 的指派是 nums.length - 1，即最後一個元素的索引，而不是 nums.length。

這二者可能出現在不同功能的二分查找中，差別是：前者相當于兩端都閉區間 [left, right]，後者相當于左閉右開區間 [left, right)，因為索引大小為 nums.length 是越界的。

我們這個算法中使用的是前者 [left, right] 兩端都閉的區間。這個區間其實就是每次進行搜尋的區間。

什麼時候應該停止搜尋呢？當然，找到了目标值的時候可以終止：

if(nums[mid] == target)
        return mid;

但如果沒找到，就需要 while 循環終止，然後傳回 -1。那 while 循環什麼時候應該終止？搜尋區間為空的時候應該終止，意味着你沒得找了，就等于沒找到嘛。

while(left <= right) 的終止條件是 left == right + 1，寫成區間的形式就是 [right + 1, right]，或者帶個具體的數字進去 [3, 2]，可見這時候區間為空，因為沒有數字既大于等于 3 又小于等于 2 的吧。是以這時候 while 循環終止是正确的，直接傳回 -1 即可。

while(left < right) 的終止條件是 left == right，寫成區間的形式就是 [left, right]，或者帶個具體的數字進去 [2, 2]，這時候區間非空，還有一個數 2，但此時 while 循環終止了。也就是說這區間 [2, 2] 被漏掉了，索引 2 沒有被搜尋，如果這時候直接傳回 -1 就是錯誤的。

當然，如果你非要用 while(left < right) 也可以，我們已經知道了出錯的原因，就打個更新檔好了：

//...
    while(left < right) {
        // ...
    }
    return nums[left] == target ? left : -1;

2、為什麼 left = mid + 1，right = mid - 1？我看有的代碼是 right = mid 或者 left = mid，沒有這些加加減減，到底怎麼回事，怎麼判斷？

答：這也是二分查找的一個難點，不過隻要你能了解前面的内容，就能夠很容易判斷。

剛才明确了「搜尋區間」這個概念，而且本算法的搜尋區間是兩端都閉的，即 [left, right]。那麼當我們發現索引 mid 不是要找的 target 時，下一步應該去搜尋哪裡呢？

當然是去搜尋 [left, mid-1] 或者 [mid+1, right] 對不對？因為 mid 已經搜尋過，應該從搜尋區間中去除。

3、此算法有什麼缺陷？

答：至此，你應該已經掌握了該算法的所有細節，以及這樣處理的原因。但是，這個算法存在局限性。

比如說給你有序數組 nums = [1,2,2,2,3]，target 為 2，此算法傳回的索引是 2，沒錯。但是如果我想得到 target 的左側邊界，即索引 1，或者我想得到 target 的右側邊界，即索引 3，這樣的話此算法是無法處理的。

這樣的需求很常見，你也許會說，找到一個 target，然後向左或向右線性搜尋不行嗎？可以，但是不好，因為這樣難以保證二分查找對數級的複雜度了。

二、尋找左側邊界的二分搜尋

常見算法

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意
    
    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

1、為什麼 while 中是 < 而不是 <=?

答：用相同的方法分析，因為 right = nums.length 而不是 nums.length - 1。是以每次循環的「搜尋區間」是 [left, right) 左閉右開。

while(left < right) 終止的條件是 left == right，此時搜尋區間 [left, left) 為空，是以可以正确終止。

PS：這裡先要說一個搜尋左右邊界和上面這個算法的一個差別，也是很多讀者問的：剛才的 right 不是 nums.length - 1 嗎，為啥這裡非要寫成 nums.length 使得「搜尋區間」變成左閉右開呢？

因為對于搜尋左右側邊界的二分查找，這種寫法比較普遍，我就拿這種寫法舉例了，保證你以後遇到這類代碼可以了解。你非要用兩端都閉的寫法反而更簡單，我會在後面寫相關的代碼，把三種二分搜尋都用一種兩端都閉的寫法統一起來，你耐心往後看就行了。

2、為什麼沒有傳回 -1 的操作？如果 nums 中不存在 target 這個值，怎麼辦？

答：因為要一步一步來，先了解一下這個「左側邊界」有什麼特殊含義：

二分查找總結一、尋找一個數二、尋找左側邊界的二分搜尋三、尋找右側邊界的二分查找四、總結

對于這個數組，算法會傳回 1。這個 1 的含義可以這樣解讀：nums 中小于 2 的元素有 1 個。

比如對于有序數組 nums = [2,3,5,7], target = 1，算法會傳回 0，含義是：nums 中小于 1 的元素有 0 個。

再比如說 nums = [2,3,5,7], target = 8，算法會傳回 4，含義是：nums 中小于 8 的元素有 4 個。

綜上可以看出，函數的傳回值（即 left 變量的值）取值區間是閉區間 [0, nums.length]，是以我們簡單添加兩行代碼就能在正确的時候 return -1：

while (left < right) {
    //...
}
// target 比所有數都大
if (left == nums.length) return -1;
// 類似之前算法的處理方式
return nums[left] == target ? left : -1;

3、為什麼 left = mid + 1，right = mid ？和之前的算法不一樣？

答：這個很好解釋，因為我們的「搜尋區間」是 [left, right) 左閉右開，是以當 nums[mid] 被檢測之後，下一步的搜尋區間應該去掉 mid 分割成兩個區間，即 [left, mid) 或 [mid + 1, right)。

4、為什麼該算法能夠搜尋左側邊界？

答：關鍵在于對于 nums[mid] == target 這種情況的處理：

if (nums[mid] == target)
        right = mid;

可見，找到 target 時不要立即傳回，而是縮小「搜尋區間」的上界 right，在區間 [left, mid) 中繼續搜尋，即不斷向左收縮，達到鎖定左側邊界的目的。

5、為什麼傳回 left 而不是 right？

答：都是一樣的，因為 while 終止的條件是 left == right。

6、能不能想辦法把 right 變成 nums.length - 1，也就是繼續使用兩邊都閉的「搜尋區間」？這樣就可以和第一種二分搜尋在某種程度上統一起來了。

答：當然可以，隻要你明白了「搜尋區間」這個概念，就能有效避免漏掉元素，随便你怎麼改都行。下面我們嚴格根據邏輯來修改：

因為你非要讓搜尋區間兩端都閉，是以 right 應該初始化為 nums.length - 1，while 的終止條件應該是 left == right + 1，也就是其中應該用 <=：

int left_bound(int[] nums, int target) {
    // 搜尋區間為 [left, right]
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // if else ...
    }

因為搜尋區間是兩端都閉的，且現在是搜尋左側邊界，是以 

left

 和 

right

 的更新邏輯如下：

if (nums[mid] < target) {
    // 搜尋區間變為 [mid+1, right]
    left = mid + 1;
} else if (nums[mid] > target) {
    // 搜尋區間變為 [left, mid-1]
    right = mid - 1;
} else if (nums[mid] == target) {
    // 收縮右側邊界
    right = mid - 1;
}

由于 while 的退出條件是 

left == right + 1

，是以當 

target

 比 

nums

 中所有元素都大時，會存在以下情況使得索引越界：

二分查找總結一、尋找一個數二、尋找左側邊界的二分搜尋三、尋找右側邊界的二分查找四、總結

是以，最後傳回結果的代碼應該檢查越界情況：

if (left >= nums.length || nums[left] != target)
    return -1;
return left;

 至此，整個算法就寫完了，完整代碼如下：

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜尋區間為 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜尋區間變為 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜尋區間變為 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收縮右側邊界
            right = mid - 1;
        }
    }
    // 檢查出界情況
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

三、尋找右側邊界的二分查找

類似尋找左側邊界的算法，這裡也會提供兩種寫法，還是先寫常見的左閉右開的寫法，隻有兩處和搜尋左側邊界不同，已标注：

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

1、為什麼這個算法能夠找到右側邊界？

答：類似地，關鍵點還是這裡：

if (nums[mid] == target) {
    left = mid + 1;

當 nums[mid] == target 時，不要立即傳回，而是增大「搜尋區間」的下界 left，使得區間不斷向右收縮，達到鎖定右側邊界的目的。

2、為什麼最後傳回 left - 1 而不像左側邊界的函數，傳回 left？而且我覺得這裡既然是搜尋右側邊界，應該傳回 right 才對。

答：首先，while 循環的終止條件是 left == right，是以 left 和 right 是一樣的，你非要展現右側的特點，傳回 right - 1 好了。

至于為什麼要減一，這是搜尋右側邊界的一個特殊點，關鍵在這個條件判斷：

if (nums[mid] == target) {
    left = mid + 1;
    // 這樣想: mid = left - 1
二分查找總結一、尋找一個數二、尋找左側邊界的二分搜尋三、尋找右側邊界的二分查找四、總結

因為我們對 left 的更新必須是 left = mid + 1，就是說 while 循環結束時，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target。

至于為什麼 left 的更新必須是 left = mid + 1，同左側邊界搜尋，就不再贅述。

3、為什麼沒有傳回 -1 的操作？如果 nums 中不存在 target 這個值，怎麼辦？

答：類似之前的左側邊界搜尋，因為 while 的終止條件是 left == right，就是說 left 的取值範圍是 [0, nums.length]，是以可以添加兩行代碼，正确地傳回 -1：

while (left < right) {
    // ...
}
if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;

4、是否也可以把這個算法的「搜尋區間」也統一成兩端都閉的形式呢？這樣這三個寫法就完全統一了，以後就可以閉着眼睛寫出來了。

答：當然可以，類似搜尋左側邊界的統一寫法，其實隻要改兩個地方就行了：

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 這裡改成收縮左側邊界即可
            left = mid + 1;
        }
    }
    // 這裡改為檢查 right 越界的情況，見下圖
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

當 

target

 比所有元素都小時，

right

 會被減到 -1，是以需要在最後防止越界：

二分查找總結一、尋找一個數二、尋找左側邊界的二分搜尋三、尋找右側邊界的二分查找四、總結

四、總結

來梳理一下這些細節差異的因果邏輯：

第一個，最基本的二分查找算法：

因為我們初始化 right = nums.length - 1
是以決定了我們的「搜尋區間」是 [left, right]
是以決定了 while (left <= right)
同時也決定了 left = mid+1 和 right = mid-1

因為我們隻需找到一個 target 的索引即可
是以當 nums[mid] == target 時可以立即傳回

第二個，尋找左側邊界的二分查找：

因為我們初始化 right = nums.length
是以決定了我們的「搜尋區間」是 [left, right)
是以決定了 while (left < right)
同時也決定了 left = mid + 1 和 right = mid

因為我們需找到 target 的最左側索引
是以當 nums[mid] == target 時不要立即傳回
而要收緊右側邊界以鎖定左側邊界

第三個，尋找右側邊界的二分查找：

因為我們初始化 right = nums.length
是以決定了我們的「搜尋區間」是 [left, right)
是以決定了 while (left < right)
同時也決定了 left = mid + 1 和 right = mid

因為我們需找到 target 的最右側索引
是以當 nums[mid] == target 時不要立即傳回
而要收緊左側邊界以鎖定右側邊界

又因為收緊左側邊界時必須 left = mid + 1
是以最後無論傳回 left 還是 right，必須減一

對于尋找左右邊界的二分搜尋，常見的手法是使用左閉右開的「搜尋區間」，我們還根據邏輯将「搜尋區間」全都統一成了兩端都閉，便于記憶，隻要修改兩處即可變化出三種寫法：

int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接傳回
            return mid;
        }
    }
    // 直接傳回
    return -1;
}

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意
    
    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别傳回，鎖定左側邊界
            right = mid - 1;
        }
    }
    // 最後要檢查 left 越界的情況
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别傳回，鎖定右側邊界
            left = mid + 1;
        }
    }
    // 最後要檢查 right 越界的情況
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

1、分析二分查找代碼時，不要出現 else，全部展開成 else if 友善了解。

2、注意「搜尋區間」和 while 的終止條件，如果存在漏掉的元素，記得在最後檢查。

3、如需定義左閉右開的「搜尋區間」搜尋左右邊界，隻要在 nums[mid] == target 時做修改即可，搜尋右側時需要減一。

4、如果将「搜尋區間」全都統一成兩端都閉，好記，隻要稍改 nums[mid] == target 條件處的代碼和傳回的邏輯即可

算法 二分查找 leetcode
上一篇: begindosetomissthepainofthetapuptothetapmicrowavemicrowavemi
下一篇: 低代碼工具：jvs-form（表單引擎）2.1.7功能清單及新增功能介紹

繼續閱讀