#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
二分查找薄坏，無重復(fù)元素
template <typename T>
int BinarySearch(vector<T> nums, T target) {? //不含有重復(fù)元素
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;
}
二分查找拓提，包含重復(fù)元素，返回第一個
template <typename T>
int BinarySearchWithDup(vector<T> nums, int target) { //包含重復(fù)元素豆拨，返回第一個相同元素
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) { // 當?shù)扔趖arget時應(yīng)該到右半部份找
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;? // 當?shù)扔趖arget時應(yīng)該到左邊找
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;
}
