#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
二分查找，无重复元素
template <typename T>
int BinarySearch(vector<T> nums, T target) { //不含有重复元素
int low = 0, high = nums.size() - 1;
while(low <= high) {
int mid = low + (high - low)/2;
if(nums[mid] == target) return mid;
else if(nums[mid] > target) {
high = mid -1;
} else {
low = mid + 1;
}
}
return -1;
}
二分查找，包含重复元素，返回第一个
template <typename T>
int BinarySearchWithDup(vector<T> nums, int target) { //包含重复元素，返回第一个相同元素
int low = 0, high = nums.size() -1;
while(low <= high) {
int mid = low + (high - low) / 2;
if(nums[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
if(nums[low] == target) return low;
return -1;
}
upper_bound
template<typename T>
int upper_bound(vector<T> &nums, T target) { // 返回第一个大于target的元素
int low = 0, high = nums.size()-1;
while(low <= high) {
int mid = low + (high - low)/2;
if(nums[mid] <= target) { // 当等于target时应该到右半部份找
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
lower_bound
template<typename T>
int lower_bound(vector<T> &nums, int target) { // 返回第一个大于或者等于target的元素
int low = 0, high = nums.size()-1;
while(low <= high) {
int mid = low + (high - low);
if(nums[mid] < target) low = mid + 1; // 当等于target时应该到左边找
else high = mid - 1;
}
return low;
}
void fakeData(vector<int> &nums, int n) {
int base = 1;
for(int i = 0; i < n; i++) {
base += rand()%10;
cout<<base<<" ";
nums.push_back(base);
}
cout<<endl;
}
int main() {
vector<int> nums;
fakeData(nums, 100);
cout<<BinarySearchWithDup(nums, 57)<<endl;
cout<<upper_bound(nums, 57)<<endl;
cout<<lower_bound(nums, 57)<<endl;
return 0;
}
