# Search for a Range

## Question

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].


## 題解

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

### Java

/**
* 本代碼fork自九章算法。沒有版權歡迎轉發。
* http://www.jiuzhang.com/solutions/search-for-a-range/
*/
public class Solution {
/**
*@param A : an integer sorted array
*@param target :  an integer to be inserted
*return : a list of length 2, [index1, index2]
*/
public ArrayList<Integer> searchRange(ArrayList<Integer> A, int target) {
ArrayList<Integer> result = new ArrayList<Integer>();
int start, end, mid;

if (A == null || A.size() == 0) {
return result;
}

// search for left bound
start = 0;
end = A.size() - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A.get(mid) == target) {
end = mid; // set end = mid to find the minimum mid
} else if (A.get(mid) > target) {
end = mid;
} else {
start = mid;
}
}
if (A.get(start) == target) {
result.set(0, start);
} else if (A.get(end) == target) {
result.set(0, end);
} else {
return result;
}

// search for right bound
start = 0;
end = A.size() - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A.get(mid) == target) {
start = mid; // set start = mid to find the maximum mid
} else if (A.get(mid) > target) {
end = mid;
} else {
start = mid;
}
}
if (A.get(end) == target) {
result.set(1, end);
} else if (A.get(start) == target) {
result.set(1, start);
} else {
return result;
}

return result;
}
}


### 源碼分析

1. 首先對輸入做異常處理，數組為空或者長度為0
2. 初始化 start, end, mid三個變量，注意mid的求值方法，可以防止兩個整型值相加時溢出
3. 使用迭代而不是遞歸進行二分查找
4. while終止條件應為start + 1 < end而不是start <= endstart == 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++

class Solution {
/**
*@param A : an integer sorted array
*@param target :  an integer to be inserted
*return : a list of length 2, [index1, index2]
*/
public:
vector<int> searchRange(vector<int> &A, int target) {
// good, fail are the result
// When found, returns good, otherwise returns fail
int N = A.size();
vector<int> fail = {-1, -1};
if(N == 0)
return fail;
vector<int> good;

// search for starting position
int lo = 0, hi = N;
while(lo < hi){
int m = lo + (hi- lo)/2;
if(A[m] < target)
lo = m + 1;
else
hi = m;
}

if(A[lo] != target)
return fail;

good.push_back(lo);

// search for ending position
lo = 0; hi = N;
while(lo < hi){
int m = lo + (hi - lo)/2;
if(target < A[m])
hi = m;
else
lo = m + 1;
}
good.push_back(lo - 1);

return good;
}
};