这道题考察二分法的细节。
其实如果不是对二分法很熟，挺容易出小错误的，写不干净。
主要考察二分法的边界条件，退出规则。
首先 先找First position.
当中间的数大于等于target时，把右边界移到m.
否则把左边界移到m + 1;
退出条件是只剩一个数。如果这个数是target, 则把l这个位置记下来，否则记 -1；
然后找last position.
当中间的数小于等于target时，把左边界移到m
否则把右边界移到m - 1;
但是你看代码里面，求m的方式在两个while loop里是略不一样的。
一个是 int m = l + (r - l) / 2;
一个是 int m = r - (r - l) / 2;
这两句话的区别是在只剩两个数的时候，第一个取左边那个，第二个是取的右边那个。
对于第一个循环，当只剩两个数a, b的时候，取了左边的那一个数a作为m，然后下一步是要么r = m , 要么l = m + 1, 都是只剩了一个数。这时如果取右边的那个数的话，r就stuck在m上了，无法退出循环。
对第二个循环，当只剩两个数a, b时，取了右边的那个数b作为m. 下一步要么是 l =m 要么是r = m - 1, 也是只剩下了一个数，可以退出循环。这时如果和第一个循环一样取左边的那个数a，l就stuck在了a (就是m）上了。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans{-1, -1};
if (nums.size() < 1) return ans;
int l = 0, r = nums.size() - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] >= target) r = m;
else l = m + 1;
}
if (nums[l] == target) ans[0] = l;
else return ans;
l = 0;
r = nums.size() - 1;
while (l < r) {
int m = r - (r - l) / 2;
if (nums[m] <= target) l = m;
else r = m - 1;
}
if (nums[l] == target) ans[1] = r;
return ans;
}
};
其实这个判断条件还可以写的更细一点，分三种
如果 nums[m] =, >, < 各写一个。但其实没多少必要。
我也写了一个这种情况下的code，帖在下面。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans{-1, -1};
if (nums.size() < 1) return ans;
int l = 0, r = nums.size() - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] == target) r = m;
else if (nums[m] < target) l = m + 1;
else r = m - 1;
}
if (nums[l] == target) ans[0] = l;
else return ans;
l = 0;
r = nums.size() - 1;
while (l < r) {
int m = r - (r - l) / 2;
if (nums[m] == target) l = m;
else if (nums[m] < target) l = m + 1;
else r = m - 1;
}
if (nums[r] == target) ans[1] = r;
return ans;
}
};
