Search for a Range.png
===================== 解題思路 =====================
這題是個綜合 first position && last position 的題目 基本就是先找 first position 如果沒找到代表根本沒有 target 在裡面 直接回傳 {-1,-1} 如果找到就先存好 res[0] 的值為 first position 接著再跑 last position (特別注意要記得 reset left 跟 right 的值)
===================== C++ code ====================
<pre><code>
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) {
// find the first position
vector<int> res(2, -1);
if(A.size() == 0) return res;
int left = 0, right = A.size() - 1;
while(left + 1 < right)
{
int mid = left + (right - left) / 2;
if(A[mid] >= target) right = mid;
else left = mid;
}
if(A[left] != target && A[right] != target) return res;
res[0] = A[left] == target? left : right;
//find the last position
left = 0;
right = A.size() - 1;
while(left + 1 < right)
{
int mid = left + (right - left) / 2;
if(A[mid] <= target) left = mid;
else right = mid;
}
res[1] = A[right] == target? right : left;
return res;
}
};
<code><pre>
