Knuth 大佬（發(fā)明 KMP 算法的那位）曾說:

Although the basic idea of binary search is comparatively straightforward,
the details can be surprisingly tricky...

這句話可以這樣理解：思路很簡單申鱼，細節(jié)是魔鬼户矢。

最常用的二分查找場景：尋找一個數(shù)请敦、尋找左側邊界蜒灰、尋找右側邊界

二分查找框架

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

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

分析二分查找的一個技巧是：不要出現(xiàn) else甲葬，而是把所有情況用 else if 寫清楚，這樣可以清楚地展現(xiàn)所有細節(jié)。
計算 mid 時需要技巧防止溢出，即 mid=left+(right-left)/2

①尋找一個數(shù)（基本的二分搜索）

搜索一個數(shù)颤陶，如果存在，返回其索引陷遮，否則返回 -1（數(shù)組已排序）

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = (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 循環(huán)的條件中是 <=滓走，而不是 < ？
因為初始化 right的賦值是 nums.length-1帽馋，即最后一個元素的索引搅方，而不是 nums.length比吭。
這二者可能出現(xiàn)在不同功能的二分查找中，區(qū)別是：前者nums.length-1相當于兩端都閉區(qū)間[left, right]姨涡，后者相當于左閉右開區(qū)間[left, right)衩藤，因為索引大小為 nums.length是越界的。
我們這個算法中使用的是前者 [left, right] 兩端都閉的區(qū)間涛漂。這個區(qū)間其實就是每次進行搜索的區(qū)間赏表，我們不妨稱為搜索區(qū)間。

什么時候應該停止搜索呢匈仗？當然瓢剿，找到了目標值的時候可以終止：

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

但如果沒找到，就需要 while 循環(huán)終止悠轩，然后返回 -1间狂。那 while 循環(huán)什么時候應該終止？
搜索區(qū)間為空的時候應該終止火架，意味著你沒得找了鉴象，就等于沒找到。

• while(left <= right)的終止條件是left == right + 1距潘，寫成區(qū)間的形式就是[right + 1, right]炼列，或者帶個具體的數(shù)字進去[3, 2]，可見這時候搜索區(qū)間為空音比，因為沒有數(shù)字既大于等于 3 又小于等于 2 的吧俭尖。所以這時候 while循環(huán)終止是正確的，直接返回 -1 即可洞翩。

• while(left < right)的終止條件是left == right稽犁，寫成區(qū)間的形式就是 [left, right]，或者帶個具體的數(shù)字進去[2, 2]骚亿，這時候搜索區(qū)間非空已亥，還有一個數(shù) 2，但此時 while 循環(huán)終止了来屠。也就是說這區(qū)間 [2, 2]被漏掉了虑椎，索引 2 沒有被搜索，如果這時候直接返回-1 就是錯誤的俱笛。

你非要用 while(left < right)也可以捆姜，我們已經(jīng)知道了出錯的原因，就打個補丁好了

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

2. 為什么 left = mid + 1迎膜，right = mid - 1泥技？我看有的代碼是right = mid或者 left = mid，沒有這些加加減減磕仅，到底怎么回事珊豹，怎么判斷簸呈？

• 答:剛才明確了搜索區(qū)間這個概念，而且本算法的搜索區(qū)間是兩端都閉的店茶，即[left, right]蜕便。那么當我們發(fā)現(xiàn)索引 mid 不是要找的 target時，如何確定下一步的搜索區(qū)間呢忽妒？
  當然是 [left, mid - 1] 或者 [mid + 1, right] 對不對玩裙？因為mid已經(jīng)搜索過，應該從搜索區(qū)間中去除段直。

3. 此算法有什么缺陷吃溅？
答：至此，你應該已經(jīng)掌握了該算法的所有細節(jié)鸯檬，以及這樣處理的原因决侈。但是，這個算法存在局限性喧务。
比如說給你有序數(shù)組nums = [1,2,2,2,3]赖歌，target = 2，此算法返回的索引是2功茴，沒錯庐冯。但是如果我想得到target的左側邊界，即索引1坎穿，或者我想得到target的右側邊界展父，即索引 3，這樣的話此算法是無法處理的玲昧。

這樣的需求很常見栖茉。你也許會說，找到一個target孵延，然后向左或向右線性搜索不行嗎吕漂？可以，但是不好尘应，因為這樣難以保證二分查找對數(shù)級的復雜度了惶凝。
我們后續(xù)的算法就來討論這兩種二分查找的算法。

②尋找左側邊界的二分搜索

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(left < right) 而不是 <= ?
答：用相同的方法分析犬钢，因為right = nums.length 而不是 nums.length - 1 梨睁。因此每次循環(huán)的「搜索區(qū)間」是[left, right)左閉右開。
while(left < right) 終止的條件是 left == right娜饵，此時搜索區(qū)間 [left, left)為空，所以可以正確終止官辈。

2. 為什么沒有返回 -1 的操作箱舞？如果 nums 中不存在 target 這個值遍坟，怎么辦？
先理解一下這個「左側邊界」有什么特殊含義：

• 對于有序數(shù)組 nums = [2,3,5,7], target = 1电湘，算法會返回 0隔节，含義是：nums 中小于 1 的元素有 0 個。
  再比如
• 對nums不變寂呛，target = 8怎诫，算法會返回 4，含義是：nums 中小于 8 的元素有 4個贷痪。

綜上可以看出
函數(shù)的返回值（即 left 變量的值）取值區(qū)間是閉區(qū)間[0, nums.length]幻妓，所以我們簡單添加兩行代碼就能在正確的時候return -1

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

3. 為什么 left = mid + 1，right = mid 劫拢？和之前的算法不一樣肉津？
這個很好解釋，因為我們的「搜索區(qū)間」是[left, right)左閉右開舱沧，所以當 nums[mid]被檢測之后妹沙，下一步的搜索區(qū)間應該去掉 mid分割成兩個區(qū)間，即 [left, mid)或[mid + 1, right)熟吏。
4.為什么該算法能夠搜索左側邊界距糖？

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

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

找到 target時不要立即返回，而是縮小「搜索區(qū)間」的上界right分俯，在區(qū)間 [left, mid)中繼續(xù)搜索肾筐，即不斷向左收縮，達到鎖定左側邊界的目的缸剪。

4.為什么返回 left 而不是 right吗铐？
都是一樣的，因為while 終止的條件是 left == right杏节。

③尋找右側邊界的二分查找

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時，不要立即返回奋渔，而是增大「搜索區(qū)間」的下界left（即縮小左邊界讓他向右靠攏镊逝，left值越大，越向右靠攏）嫉鲸，使得區(qū)間不斷向右收縮撑蒜，達到鎖定右側邊界的目的
2. 為什么最后返回 left - 1 而不像左側邊界的函數(shù)，返回 left？而且我覺得這里既然是搜索右側邊界座菠，應該返回 right 才對狸眼。
首先，while循環(huán)的終止條件是 left == right浴滴，所以 left和right是一樣的拓萌，你非要體現(xiàn)右側的特點，返回 right - 1好了升略。
至于為什么要減一微王，這是搜索右側邊界的一個特殊點，關鍵在這個條件判斷：

if (nums[mid] == target) {
    left = mid + 1;
    // 這樣想: mid = left - 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;

④最后總結

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

因為我們初始化 right = nums.length - 1
所以決定了我們的「搜索區(qū)間」是 [left, right]
所以決定了 while (left <= right)
同時也決定了 left = mid+1 和 right = mid-1
因為我們只需找到一個 target 的索引即可
所以當 nums[mid] == target 時可以立即返回

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

因為我們初始化 right = nums.length
所以決定了我們的「搜索區(qū)間」是 [left, right)
所以決定了 while (left < right)
同時也決定了 left = mid + 1 和 right = mid
因為我們需找到 target 的最左側索引
所以當 nums[mid] == target 時不要立即返回
而要縮小右側邊界 right = mid;以鎖定左側邊界

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

因為我們初始化 right = nums.length
所以決定了我們的「搜索區(qū)間」是 [left, right)
所以決定了 while (left < right)
同時也決定了 left = mid + 1 和 right = mid
因為我們需找到 target 的最右側索引
所以當 nums[mid] == target 時不要立即返回
而要收緊左側邊界以鎖定右側邊界
又因為收緊左側邊界（要增大left）時必須 left = mid + 1
所以最后無論返回 left 還是 right靠闭，必須減一

參考文章連接:傳送門