68 lines
1.3 KiB
C++
68 lines
1.3 KiB
C++
#include "s0034_find_first_and_last_position_of_element_in_sorted_array.hpp"
|
|
|
|
// 闭区间写法
|
|
vector<int> S0034::searchRange1(vector<int>& nums, int target) {
|
|
int len = nums.size();
|
|
int l{0};
|
|
int r = len - 1;
|
|
while (l <= r) {
|
|
int m = (l + r) >> 1;
|
|
if (target < nums[m]) {
|
|
r = m - 1;
|
|
} else if (nums[m] < target) {
|
|
l = m + 1;
|
|
} else {
|
|
l = r = m;
|
|
while (l >= 0) {
|
|
if (nums[l] == target) {
|
|
--l;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
while (r <= len - 1) {
|
|
if (nums[r] == target) {
|
|
++r;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
return vector<int>{l + 1, r - 1};
|
|
}
|
|
}
|
|
return vector<int>{-1, -1};
|
|
}
|
|
|
|
// 开区间写法
|
|
vector<int> S0034::searchRange2(vector<int>& nums, int target) {
|
|
int len = nums.size();
|
|
int l{0};
|
|
int r = len;
|
|
while (l < r) {
|
|
int m = (l + r) >> 1;
|
|
if (target < nums[m]) {
|
|
r = m;
|
|
} else if (nums[m] < target) {
|
|
l = m + 1;
|
|
} else {
|
|
l = r = m;
|
|
while (l >= 0) {
|
|
if (nums[l] == target) {
|
|
--l;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
while (r <= len - 1) {
|
|
if (nums[r] == target) {
|
|
++r;
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
return vector<int>{l + 1, r - 1};
|
|
}
|
|
}
|
|
return vector<int>{-1, -1};
|
|
}
|