Search for a Range

Question

  1. Given a sorted array of integers, find the starting and ending position of a given target value.
  3. Your algorithm's runtime complexity must be in the order of O(log n).
  5. If the target is not found in the array, return [-1, -1].
  7. Example
  8. Given [5, 7, 7, 8, 8, 10] and target value 8,
  9. return [3, 4].

題解

Search for a range 的題目可以拆解為找 first & last position 的題目，即要做兩次二分。由上題二分查找可找到滿足條件的左邊界，因此只需要再將右邊界找出即可。注意到在(target == nums[mid]時賦值語句為end = mid，將其改為start = mid即可找到右邊界，解畢。

Java

  1. /**
  2.  * 本代碼fork自九章算法。沒有版權歡迎轉發。
  3.  * http://www.jiuzhang.com/solutions/search-for-a-range/
  4.  */
  5. public class Solution {
  6.     /**
  7.      *@param A : an integer sorted array
  8.      *@param target :  an integer to be inserted
  9.      *return : a list of length 2, [index1, index2]
  10.      */
  11.     public ArrayList<Integer> searchRange(ArrayList<Integer> A, int target) {
  12.         ArrayList<Integer> result = new ArrayList<Integer>();
  13.         int start, end, mid;
  14.         result.add(-1);
  15.         result.add(-1);
  17.         if (A == null || A.size() == 0) {
  18.             return result;
  19.         }
  21.         // search for left bound
  22.         start = 0;
  23.         end = A.size() - 1;
  24.         while (start + 1 < end) {
  25.             mid = start + (end - start) / 2;
  26.             if (A.get(mid) == target) {
  27.                 end = mid; // set end = mid to find the minimum mid
  28.             } else if (A.get(mid) > target) {
  29.                 end = mid;
  30.             } else {
  31.                 start = mid;
  32.             }
  33.         }
  34.         if (A.get(start) == target) {
  35.             result.set(0, start);
  36.         } else if (A.get(end) == target) {
  37.             result.set(0, end);
  38.         } else {
  39.             return result;
  40.         }
  42.         // search for right bound
  43.         start = 0;
  44.         end = A.size() - 1;
  45.         while (start + 1 < end) {
  46.             mid = start + (end - start) / 2;
  47.             if (A.get(mid) == target) {
  48.                 start = mid; // set start = mid to find the maximum mid
  49.             } else if (A.get(mid) > target) {
  50.                 end = mid;
  51.             } else {
  52.                 start = mid;
  53.             }
  54.         }
  55.         if (A.get(end) == target) {
  56.             result.set(1, end);
  57.         } else if (A.get(start) == target) {
  58.             result.set(1, start);
  59.         } else {
  60.             return result;
  61.         }
  63.         return result;
  64.         // write your code here
  65.     }
  66. }

源碼分析

  1. 首先對輸入做異常處理，數組為空或者長度為0
  2. 初始化 start, end, mid三個變量，注意mid的求值方法，可以防止兩個整型值相加時溢出
  3. 使用迭代而不是遞歸進行二分查找
  4. while終止條件應為start + 1 < end而不是start <= end，start == end時可能出現死循環
  5. 先求左邊界，迭代終止時先判斷A.get(start) == target，再判斷A.get(end) == target，因為迭代終止時target必取start或end中的一個，而end又大於start，取左邊界即為start.
  6. 再求右邊界，迭代終止時先判斷A.get(end) == target，再判斷A.get(start) == target
  7. 兩次二分查找除了終止條件不同，中間邏輯也不同，即當A.get(mid) == target如果是左邊界（first postion），中間邏輯是end = mid；若是右邊界（last position），中間邏輯是start = mid
  8. 兩次二分查找中間勿忘記重置 start, end 的變量值。

C++

  1. class Solution {
  2.     /** 
  3.      *@param A : an integer sorted array
  4.      *@param target :  an integer to be inserted
  5.      *return : a list of length 2, [index1, index2]
  6.      */
  7. public:
  8.     vector<int> searchRange(vector<int> &A, int target) {
  9.         // good, fail are the result
  10.         // When found, returns good, otherwise returns fail
  11.         int N = A.size();
  12.         vector<int> fail = {-1, -1};
  13.         if(N == 0) 
  14.             return fail;
  15.         vector<int> good;
  17.         // search for starting position
  18.         int lo = 0, hi = N;
  19.         while(lo < hi){
  20.             int m = lo + (hi- lo)/2;
  21.             if(A[m] < target)
  22.                 lo = m + 1;
  23.             else
  24.                 hi = m;
  25.         }
  27.         if(A[lo] != target) 
  28.             return fail;
  30.         good.push_back(lo);
  32.         // search for ending position
  33.         lo = 0; hi = N;
  34.         while(lo < hi){
  35.             int m = lo + (hi - lo)/2;
  36.             if(target < A[m])
  37.                 hi = m;
  38.             else
  39.                 lo = m + 1;
  40.         }
  41.         good.push_back(lo - 1);
  43.         return good;
  44.     }
  45. };

源碼分析

與前面題目類似，此題是將兩個子題組合起來，前半為找出”不小於target的最左元素”，後半是”不大於target的最右元素”，同樣的，使用開閉區間[lo, hi)仍然可以簡潔的處理各種邊界條件，僅須注意在解第二個子題”不大於target的最右元素”時，由於每次lo更新時都至少加1，最後會落在我們要求的位置的下一個，因此記得減1回來，若直覺難以理解，可以使用一個例子在紙上推一次每個步驟就可以體會。