簡介

二分查找（Binary Search）算法，也叫折半查找算法。在給順序表結構中（也就是數組）快速查找某一個值或者某個區(qū)間。二分查找的時間復雜度是O(logn)。雖然二分查找看起來很簡單，實現出來的代碼不夠寥寥十幾行，但是就是會出錯，要么漏個等號，要么少加1。也就是思路很簡單，細節(jié)是魔鬼

本文均抄自Leetcode精選解題，本文原作者是labuladong

模版

二分查找的寫法基本固定，根據不同的場景修改起始值、判斷條件、中止值非常容易忽略細節(jié)

function binarySearch(nums, target) {
    let left = 0, 
    let right = ...;

    while(...) {
        let mid = parseInt((right + left) / 2); // 向下取整
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

關于mid的取值問題，mid=（right+left）/2是有問題的，因為當right和left比較大的時候，相加的值有可能導致溢出。改進的方法是寫成mid = left + (right-left)/2。如果要進行極致的性能優(yōu)化，可以將除以2的操作寫成位運算，left + (right-left) >> 1，相比于除法，計算機計算位運算的速度更快。

本文均寫成(right + left) / 2方便閱讀，給定的數組均是升序數組

查找某一固定值

在給定的升序數組中，查找該數組中的某一個值，返回該值在數組中所處下標位置，若不存在該值則返回-1

例：給定數組[1,3,4,6,9,11,23,55]，查找數字6

function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length-1;

    while(left<=right) {
        let mid = parseInt((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;
}

• 為什么 while 循環(huán)的條件中是 <=，而不是 < ？

  因為right初始化的值是nums.length-1，即數組中最后一個元素，而不是nums.length。

  這二者可能出現在不同功能的二分查找中，區(qū)別是：前者相當于兩端都閉區(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]，或者帶個具體的數字進去 [3, 2]，可見這時候搜索區(qū)間為空，因為沒有數字既大于等于 33 又小于等于 22 的吧。所以這時候 while 循環(huán)終止是正確的，直接返回 -1 即可。

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

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

  這也是二分查找的一個難點，不過只要你能理解前面的內容，就能夠很容易判斷。

  剛才明確了「搜索區(qū)間」這個概念，而且本算法的搜索區(qū)間是兩端都閉的，即 [left, right]。那么當我們發(fā)現索引 mid 不是要找的 target 時，如何確定下一步的搜索區(qū)間呢？

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

查找第一個等于給定元素的值(左邊界)

類似于上一個例子，現在我們給定的數組變成了[1,6,6,6,9]，需要返回第一個等于6的元素的下標。運行上面的函數返回值為2，因為第一個值的mid就等于了6。那么如何改進二分查找，才能找到第一個等于6的元素呢？

function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length;

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

• 為什么 while(left < right) 而不是 <= ?

  用相同的方法分析，因為 right = nums.length 而不是 nums.length - 1。因此每次循環(huán)的「搜索區(qū)間」是 [left, right) 左閉右開。

  while(left < right)終止的條件是 left == right，此時搜索區(qū)間 [left, left) 為空，所以可以正確終止。

• 為什么沒有返回 -1 的操作？如果 nums 中不存在 target 這個值，怎么辦？

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

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

  再比如說 nums 不變，target = 8，算法會返回 4，含義是：nums 中小于 8 的元素有 4 個。

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

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

• 為什么 left = mid + 1，right = mid ？和之前的算法不一樣？

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

• 為什么該算法能夠搜索左側邊界？

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

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

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

查找最后一個等于給定元素的值(右邊界)

function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length;

    while(left<right) {
        let mid = parseInt((right + left) / 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;
}

• 為什么最后返回 left - 1 而不像左側邊界的函數，返回 left？而且我覺得這里既然是搜索右側邊界，應該返回 right 才對。

  首先，while 循環(huán)的終止條件是 left == right，所以 left 和 right 是一樣的，你非要體現右側的特點，返回 right - 1 好了。

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

學習心得

二分查找對于有序數組的查詢效率非常高，但是對于邊界問題處理上十分棘手，考察細節(jié)一不小心就會導致死循環(huán)，而且不易查找錯誤。

有效的理解是確定每次的搜索范圍以及循環(huán)中止條件。對于每次修改搜索范圍的原則是，關注mid有沒有被搜索過。在此基礎上+1或者-1。

參考資料

• leetcode精選解題

• 極客時間 二分查找