Binary Search - 二分搜尋

Question

  1. Binary search is a famous question in algorithm.
  3. For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.
  5. If the target number does not exist in the array, return -1.
  7. Example
  8. If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.
  10. Challenge
  11. If the count of numbers is bigger than MAXINT, can your code work properly?

題解

對於已排序升序陣列，使用二分搜尋可滿足複雜度要求，注意陣列中可能有重複值。

Java

  1. /**
  2.  * 本代碼fork自九章算法。沒有版權歡迎轉發。
  3.  * http://www.jiuzhang.com//solutions/binary-search/
  4.  */
  5. class Solution {
  6.     /**
  7.      * @param nums: The integer array.
  8.      * @param target: Target to find.
  9.      * @return: The first position of target. Position starts from 0.
  10.      */
  11.     public int binarySearch(int[] nums, int target) {
  12.         if (nums == null || nums.length == 0) {
  13.             return -1;
  14.         }
  16.         int start = 0;
  17.         int end = nums.length - 1;
  18.         int mid;
  19.         while (start + 1 < end) {
  20.             mid = start + (end - start) / 2; // avoid overflow when (end + start)
  21.             if (target < nums[mid]) {
  22.                 end = mid;
  23.             } else if (target > nums[mid]) {
  24.                 start = mid;
  25.             } else {
  26.                 end = mid;
  27.             }
  28.         }
  30.         if (nums[start] == target) {
  31.             return start;
  32.         }
  33.         if (nums[end] == target) {
  34.             return end;
  35.         }
  37.         return -1;
  38.     }
  39. }

源碼分析

  1. 首先對輸入做異常處理，陣列為空或者長度為0。
  2. 初始化 start, end, mid三個變量，注意mid的求值方法，可以防止兩個整型值相加時溢出。
  3. 使用迭代而不是遞迴進行二分搜尋，因為工程中遞迴寫法存在潛在溢出的可能。
  4. while終止條件應為start + 1 < end而不是start <= end，start == end時可能出現死循環。即循環終止條件是相鄰或相交元素時退出。
  5. 迭代終止時target應為start或者end中的一個——由上述循環終止條件有兩個，具體誰先誰後視題目是找 first position or last position 而定。
  6. 賦值語句end = mid有兩個條件是相同的，可以選擇寫到一塊。
  7. 配合while終止條件start + 1 < end（相鄰即退出）的賦值語句mid永遠沒有+1或者-1，這樣不會死循環。

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param nums: The integer array.
  5.      * @param target: Target number to find.
  6.      * @return: The first position of target. Position starts from 0. 
  7.      */
  8.     int binarySearch(vector<int> &nums, int target) {
  9.         if( nums.size() == 0 ) return -1;
  11.         int lo = 0, hi = nums.size();
  12.         while(lo < hi){
  13.             int mi = lo + (hi - lo)/2;
  14.             if(nums[mi] < target)
  15.                 lo = mi + 1;
  16.             else
  17.                 hi = mi;
  18.         }
  20.         if(nums[lo] == target) return lo;
  21.         return -1;
  22.     }
  23. };

源碼分析

遇到需要處理陣列範圍的問題，由於C/C++語言本身的特性，統一使用開閉區間表示index範圍將有許多好處，[lo, hi)表示包含lo但不包含hi的區間。比方說，如果要遍歷這個區間，迴圈的條件可以寫為for(i = lo; i < hi; i++)這類常用的方式，如果要求此段區間長度可用int length = hi - lo;，另外在很多邊界條件的判斷上也會比較簡潔。實際上在STL裡的iterator也是使用了用類似的概念，一個容器的end()表示的是一個已經超出指定範圍的iterator。以此題來說，可以看出C++的實現方法確實比較簡潔。

  1. 終止條件簡單設定為lo < hi，事實上觀察調整lo與hi範圍的過程，終止的時候一定是lo == hi。
  2. 觀察lo的更新條件，是當nums[mi]比目標值小時將lo更新為mi + 1，也就是說，lo可以保證下界一定會不斷排除比target小的值，其餘狀況每次循環hi則減少範圍，因此等到循環終止之後，lo就會指到不小於target的最小元素，我們再將這個元素與target比較，就知道是否有找到，沒有的話就返回-1