First Time
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int size = nums.size();
int lo = 0, hi = size - 1;
int pos = -1;
while(lo <= hi)
{
int medium = (hi + lo) / 2;
if(nums[medium] < target)
{
lo = medium + 1;
}else if(nums[medium] > target)
{
hi = medium - 1;
}else
{
pos = medium;
while (pos > 0 && nums[pos] == nums[pos - 1]) --pos;
break;
}
}
if(pos == -1) return {-1, -1};
int i = pos + 1;
while(i < size)
{
if(nums[i] != target)
break;
else
++i;
}
return {pos, i - 1};
}
};
|
Second time
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int size = nums.size();
int lo = 0, hi = size - 1;
int posL = -1, posR = -1;
while(lo <= hi)
{
int medium = (hi + lo) / 2;
if(nums[medium] < target)
{
lo = medium + 1;
}else if(nums[medium] > target)
{
hi = medium - 1;
}else
{
posL = posR = medium;
while (posL > 0 && nums[posL] == nums[posL - 1]) --posL;
while (posR < size - 1 && nums[posR] == nums[posR + 1]) ++posR;
break;
}
}
return {posL, posR};
}
};
|
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = binarySearch(nums, target, true);
if(left == nums.size() || nums[left] != target)
return {-1, -1};
return {left, binarySearch(nums, target, false) - 1};
}
private:
int binarySearch(vector<int>& nums, int target, bool isLeft)
{
int lo = 0, hi = nums.size();
while(lo < hi)
{
int med = (lo + hi) / 2;
if(nums[med] > target || (isLeft && nums[med] == target))
{
hi = med;
}else
{
lo = med + 1;
}
}
return lo;
}
};
|
review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.empty())
return {-1, -1};
int lo = 0, hi = nums.size() - 1;
while(lo < hi)
{
int mid = (lo + hi) / 2;
if(nums[mid] < target)
lo = mid + 1;
else
hi = mid;
}
if(nums[lo] != target)
return {-1, -1};
int left = lo;
lo = 0;
hi = nums.size() - 1;
while(lo < hi)
{
int mid = (lo + hi) / 2 + 1;
if(nums[mid] <= target)
lo = mid;
else
hi = mid - 1;
}
return {left, hi};
}
};
|
其中第一次往左找，第二次的mid+1是为了使mid偏向右边，从而找到最右的