《算法與資料結構》學習筆記13---二分查找

前言

    此内容為本人學習筆記。

正文

    針對有序資料集合的查找算法：二分查找（Binary Search）算法，也叫折半查找算法。二分查找是一種非常簡單易懂的快速查找算法，生活中到處可見。比如說，有一個猜字遊戲。一人随機寫一個 0 到 99 之間的數字，然後另一人來猜第一個人寫的是什麼。猜的過程中，每猜一次，就會告訴第二個人猜的大了還是小了，直到猜出結果為止。

假設隻有 10 個訂單，訂單金額分别是：8，11，19，23，27，33，45，55，67，98。現在要打到金額等于19的訂單。利用二分思想，每次都與區間的中間資料對比大小，縮小查找區間的範圍。

    二分查找針對的是一個有序的資料集合，查找思想有點類似分治思想。每次都通過跟區間的中間元素對比，将待查找的區間縮小為之前的一半，直到找到要查找的元素，或者區間被縮小為 0。

O(logn)驚人的查找速度

    二分查找是一種非常高效的查找算法。現在假設資料大小是n，每次查找後資料都會縮小為原來的一半，也是會除以2.最壞情況下，直到查找區間被縮小為空。才停止。

被查找區間的大小變化：

                        n, n/2, n/4, …, n/(2k)

    可以看出來，這是一個等比數列。其中 n/2k=1 時，k 的值就是總共縮小的次數。而每一次縮小操作隻涉及兩個資料的大小比較，是以，經過了 k 次區間縮小操作，時間複雜度就是 O(k)。通過 n/2k=1，可以求得 k=log2n，是以時間複雜度就是 O(logn)。

     O(logn) 這種對數時間複雜度是一種極其高效的時間複雜度，有的時候甚至比時間複雜度是常量級 O(1) 的算法還要高效。為什麼這麼說呢？

    因為 logn 是一個非常“恐怖”的數量級，即便 n 非常非常大，對應的 logn 也很小。比如 n 等于 2 的 32 次方，大約是 42 億。也就是說，如果在 42 億個資料中用二分查找一個資料，最多需要比較 32 次。用大 O 标記法表示時間複雜度的時候，會省略掉常數、系數和低階。對于常量級時間複雜度的算法來說，O(1) 有可能表示的是一個非常大的常量值，比如 O(1000)、O(10000)。是以，常量級時間複雜度的算法有時候可能還沒有 O(logn) 的算法執行效率高。

二分查找的遞歸與非遞歸實作

    簡單的二分查找并不難，難的是二分查找的變體問題。

    最簡單的情況就是有序數組中不存在重複元素，java代碼實作一個最簡單的二分查找算法。

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;

  while (low <= high) {
    int mid = (low + high) / 2;
    if (a[mid] == value) {
      return mid;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}
           

    low、high、mid 都是指數組下标，其中 low 和 high 表示目前查找的區間範圍，初始 low=0， high=n-1。mid 表示 [low, high] 的中間位置。通過對比 a[mid] 與 value 的大小，來更新接下來要查找的區間範圍，直到找到或者區間縮小為 0，就退出。

    容易出錯的地方：1.循環退出條件是 low<=high，而不是 low<high；2.實際上，mid=(low+high)/2 這種寫法是有問題的。因為如果 low 和 high 比較大的話，兩者之和就有可能會溢出。改進的方法是将 mid 的計算方式寫成 low+(high-low)/2。更進一步，如果要将性能優化到極緻的話，可以将這裡的除以 2 操作轉化成位運算 low+((high-low)>>1)。因為相比除法運算來說，計算機處理位運算要快得多；3.low=mid+1，high=mid-1。注意這裡的 +1 和 -1，如果直接寫成 low=mid 或者 high=mid，就可能會發生死循環。比如，當 high=3，low=3 時，如果 a[3] 不等于 value，就會導緻一直循環不退出。

    實際上，二分查找除了用循環實作，還可以用遞歸來實作。

// 二分查找的遞歸實作
public int bsearch(int[] a, int n, int val) {
  return bsearchInternally(a, 0, n - 1, val);
}

private int bsearchInternally(int[] a, int low, int high, int value) {
  if (low > high) return -1;

  int mid =  low + ((high - low) >> 1);
  if (a[mid] == value) {
    return mid;
  } else if (a[mid] < value) {
    return bsearchInternally(a, mid+1, high, value);
  } else {
    return bsearchInternally(a, low, mid-1, value);
  }
}
           

二分查找應用場景的局限性

1. 二分查找依賴的是順序表結構，就是數組。

       二分查找能否依賴其他資料結構呢？比如連結清單。答案是不可以的，主要原因是二分查找算法需要按照下标随機通路元素。數組按照下标随機通路資料的時間複雜度是 O(1)，而連結清單随機通路的時間複雜度是 O(n)。是以，如果資料使用連結清單存儲，二分查找的時間複雜就會變得很高。二分查找隻能用在資料是通過順序表來存儲的資料結構上。如果資料是通過其他資料結構存儲的，則無法應用二分查找。

2. 二分查找針對的是有序數組

       二分查找對這一點的要求比較苛刻，資料必須是有序的。如果資料沒有序，我們需要先排序。前面章節裡我們講到，排序的時間複雜度最低是 O(nlogn)。是以，如果我們針對的是一組靜态的資料，沒有頻繁地插入、删除，我們可以進行一次排序，多次二分查找。這樣排序的成本可被均攤，二分查找的邊際成本就會比較低。

   但是，如果我們的資料集合有頻繁的插入和删除操作，要想用二分查找，要麼每次插入、删除操作之後保證資料仍然有序，要麼在每次二分查找之前都先進行排序。針對這種動态資料集合，無論哪種方法，維護有序的成本都是很高的。

   是以，二分查找隻能用在插入、删除操作不頻繁，一次排序多次查找的場景中。針對動态變化的資料集合，二分查找将不再适用。

3. 資料量太小不适合二分查找

       如果要處理的資料量很小，完全沒有必要用二分查找，順序周遊就足夠了。比如我們在一個大小為 10 的數組中查找一個元素，不管用二分查找還是順序周遊，查找速度都差不多。隻有資料量比較大的時候，二分查找的優勢才會比較明顯。

   不過，這裡有一個例外。如果資料之間的比較操作非常耗時，不管資料量大小，都推薦使用二分查找。比如，數組中存儲的都是長度超過 300 的字元串，如此長的兩個字元串之間比對大小，就會非常耗時。需要盡可能地減少比較次數，而比較次數的減少會大大提高性能，這個時候二分查找就比順序周遊更有優勢。

4. 資料量太大也不适合二分查找

       二分查找的底層需要依賴數組這種資料結構，而數組為了支援随機通路的特性，要求記憶體空間連續，對記憶體的要求比較苛刻。比如，我們有 1GB 大小的資料，如果希望用數組來存儲，那就需要1GB的連續記憶體空間。即便有 2GB 的記憶體空間剩餘，但是如果這剩餘的 2GB 記憶體空間都是零散的，沒有連續的 1GB 大小的記憶體空間，那照樣無法申請一個 1GB 大小的數組。而二分查找是作用在數組這種資料結構之上的，是以太大的資料用數組存儲就比較吃力了，也就不能用二分查找了。

如果資料使用連結清單存儲，二分查找的時間複雜就會變得很高，那查找的時間複雜度究竟是多少呢？

假設連結清單長度為n，二分查找每次都要找到中間點(計算中忽略奇偶數差異):

第一次查找中間點，需要移動指針n/2次；

第二次，需要移動指針n/4次；

第三次需要移動指針n/8次；

…

以此類推，一直到1次為值

總共指針移動次數(查找次數) = n/2 + n/4 + n/8 + …+ 1，這顯然是個等比數列，根據等比數列求和公式：Sum = n - 1.

最後算法時間複雜度是：O(n-1)，忽略常數，記為O(n)，時間複雜度和順序查找時間複雜度相同

但是稍微思考下，在二分查找的時候，由于要進行多餘的運算，嚴格來說，會比順序查找時間慢。

四種常見的二分查找變形問題

• 查找第一個值等于給定值的元素
• 查找最後一個值等于給定值的元素
• 查找第一個大于等于給定值的元素
• 查找最後一個小于等于給定值的元素

前提：資料都是從小到大排序的

變體一：查找第一個值等于給定值的元素

    之前的二分查找是最簡單的一種，即有序資料集合中不存在重複的資料，我們在其中查找值等于某個給定值的資料。但是如果 有序資料集合中存在重複的資料，并且我們希望找到第一個值等于給定值的資料 ，之前講的就不能正常工作了。

    一個有序數組： a[10] 1、3、4、5、6、7、8、8、8、11、18 此時需要查找第一個等于8的資料。

    首先拿 8 與區間的中間值 a[4] 比較，8 比 6 大，于是在下标 5 到 9 之間繼續查找。下标 5 和 9 的中間位置是下标 7，a[7] 正好等于 8，是以代碼就傳回了。盡管 a[7] 也等于 8，但它并不是我們想要找的第一個等于 8 的元素，因為第一個值等于 8 的元素是數組下标為 5 的元素。

給出一種實作方法：

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}
           

    a[mid] 跟要查找的 value 的大小關系有三種情況：大于、小于、等于。對于 a[mid]>value 的情況，我們需要更新 high= mid-1；對于 a[mid]<value 的情況，我們需要更新 low=mid+1。這兩點都很好了解。那當 a[mid]=value 的時候應該如何處理呢？

    如果我們查找的是任意一個值等于給定值的元素，當 a[mid] 等于要查找的值時，a[mid] 就是我們要找的元素。但是，如果我們求解的是第一個值等于給定值的元素，當 a[mid] 等于要查找的值時，我們就需要确認一下這個 a[mid] 是不是第一個值等于給定值的元素。

    看第 11 行代碼。如果 mid 等于 0，那這個元素已經是數組的第一個元素，那它肯定是要找的；如果 mid 不等于 0，但 a[mid] 的前一個元素 a[mid-1] 不等于 value，那也說明 a[mid] 就是要找的第一個值等于給定值的元素。

    如果經過檢查之後發現 a[mid] 前面的一個元素 a[mid-1] 也等于 value，那說明此時的 a[mid] 肯定不是要查找的第一個值等于給定值的元素。那就更新 high=mid-1，因為要找的元素肯定出現在 [low, mid-1] 之間。

變體二：查找最後一個值等于給定值的元素

    與之前查找第一個元素類似，這裡先給出示例：

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}
           

    還是看第 11 行代碼：

1. 如果 a[mid] 這個元素已經是數組中的最後一個元素了，那它肯定是要找的；
2. 如果 a[mid] 的後一個元素 a[mid+1] 不等于 value，那也說明 a[mid] 就是要找的最後一個值等于給定值的元素。2. 如果 a[mid] 的後一個元素 a[mid+1] 不等于 value，那也說明 a[mid] 就是要找的最後一個值等于給定值的元素。
3. 如果經過檢查之後，發現 a[mid] 後面的一個元素 a[mid+1] 也等于 value，那說明目前的這個 a[mid] 并不是最後一個值等于給定值的元素。就更新 low=mid+1，因為要找的元素肯定出現在 [mid+1, high] 之間。3. 如果經過檢查之後，發現 a[mid] 後面的一個元素 a[mid+1] 也等于 value，那說明目前的這個 a[mid] 并不是最後一個值等于給定值的元素。就更新 low=mid+1，因為要找的元素肯定出現在 [mid+1, high] 之間。

變體三：查找第一個大于等于給定值的元素

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] >= value) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}
           

1. 如果 a[mid] 小于要查找的值 value，那要查找的值肯定在 [mid+1, high] 之間，是以，我們更新 low=mid+1。
2. 對于 a[mid] 大于等于給定值 value 的情況，我們要先看下這個 a[mid] 是不是我們要找的第一個值大于等于給定值的元素。如果 a[mid] 前面已經沒有元素，或者前面一個元素小于要查找的值 value，那 a[mid] 就是我們要找的元素。這段邏輯對應的代碼是第 7 行。
3. 如果 a[mid-1] 也大于等于要查找的值 value，那說明要查找的元素在 [low, mid-1] 之間，是以，我們将 high 更新為 mid-1。

變體四：查找最後一個小于等于給定值的元素

public int bsearch7(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}
           

    通過IP位址來查找IP歸屬地的功能，相信都用過。沒用過也沒關系，你現在可以打開百度，在搜尋框裡随便輸一個 IP 位址，就會看到它的歸屬地。這個功能并不複雜，它是通過維護一個很大的 IP 位址庫來實作的。位址庫中包括 IP 位址範圍和歸屬地的對應關系。

    當想要查詢 202.102.133.13 這個 IP 位址的歸屬地時，就在位址庫中搜尋，發現這個 IP 位址落在 [202.102.133.0, 202.102.133.255] 這個位址範圍内，那就可以将這個 IP 位址範圍對應的歸屬地“山東東營市”顯示給使用者了。

[202.102.133.0, 202.102.133.255]  山東東營市 
[202.102.135.0, 202.102.136.255]  山東煙台 
[202.102.156.34, 202.102.157.255] 山東青島 
[202.102.48.0, 202.102.48.255] 江蘇宿遷 
[202.102.49.15, 202.102.51.251] 江蘇泰州 
[202.102.56.0, 202.102.56.255] 江蘇連雲港
           

    在龐大的位址庫中逐一比對 IP 位址所在的區間，是非常耗時的。假設有 12 萬條這樣的 IP 區間與歸屬地的對應關系，如何快速定位出一個 IP 位址的歸屬地呢？

    現在這個問題應該很簡單了。如果 IP 區間與歸屬地的對應關系不經常更新，可以先預處理這 12 萬條資料，讓其按照起始 IP 從小到大排序。如何來排序呢？因為IP 位址可以轉化為 32 位的整型數。是以，可以将起始位址，按照對應的整型值的大小關系，從小到大進行排序。

    然後，這個問題就可以轉化為第四種變形問題“在有序數組中，查找最後一個小于等于某個給定值的元素”了。

    當要查詢某個 IP 歸屬地時，可以先通過二分查找，找到最後一個起始 IP 小于等于這個 IP 的 IP 區間，然後，檢查這個 IP 是否在這個 IP 區間内，如果在，就取出對應的歸屬地顯示；如果不在，就傳回未查找到。