Leetcode 34 Find First and Last Position of Element in Sorted Array
题意：找到非严格递增的数组中和target相等的左右边界https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
解答： 经典二分，找左右边界，要查看l是否满足题意
class Solution {
public:
vector<int> searchRange(vector<int>& a, int t) {
if (a.empty()) return {-1, -1};
int first = findFirst(a, t);
int second = findLast(a , t);
return {first, second};
}
int findFirst(vector<int>& a, int t) {
int l = 0;
int r = a.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if(a >= t) {
r = mid;
} else {
l = mid + 1;
}
}
return a == t ? l : -1;
}
int findLast(vector<int>& a, int t) {
int l = 0;
int r = a.size() - 1;
while (l < r) {
int mid = l + (r - l) + 1 / 2;
if(a <= t) {
l = mid;
} else {
r = mid - 1;
}
}
return a == t ? l : -1;
}
};
算法复杂度：O(2logN), N是数组长度，空间复杂度O（1）
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]