給定一個(gè)包含 n 個(gè)整數(shù)的排序數(shù)組搬素，找出給定目標(biāo)值 target 的起始和結(jié)束位置
1魏保、查找target的起始位置
int searchStartPos(vector<int> vec, int target) {
int low = 0;
int high = vec.size() - 1;
while (low < high) { //注意不是 <=, 不然會(huì)死循環(huán)
int mid = (low + high) / 2;
if (vec[mid] >= target) {
high = mid;
} else {
low = mid + 1;
}
}
if (vec[high] == target) {
return high;
} else {
return -1;
}
}
2谓罗、查找target的結(jié)束位置
int searchEndPos(vector<int> vec, int target) {
int low = 0;
int high = vec.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
if (vec[mid] <= target) {
low = mid + 1;
} else {
high = mid;
}
}
if (vec[low - 1] == target) {
return low - 1;
} else {
return -1;
}
}
leetcode 61. 搜索區(qū)間:
給定一個(gè)包含 n 個(gè)整數(shù)的排序數(shù)組檩咱，找出給定目標(biāo)值 target 的起始和結(jié)束位置刻蚯。
https://www.lintcode.com/problem/search-for-a-range/description
leetcode 462. 目標(biāo)出現(xiàn)總和:
給一個(gè)升序的數(shù)組桑嘶，以及一個(gè)target，找到它在數(shù)組中出現(xiàn)的次數(shù)讨便。
https://www.lintcode.com/problem/total-occurrence-of-target/description
