二分答案模板
程序员文章站
2024-03-17 17:14:52
...
#include <iostream>
using namespace std;
int a[] = {1, 2, 4, 5, 7, 8};
//返回最后一个小于k的数的下标
int find1(int k) {
int l = 0, r = 5;
while(l < r) {
int mid = l + r + 1 >> 1;
if(a[mid] < k) l = mid;
else r = mid - 1;
}
return l;
}
//返回最后一个小于等于k的数的下标
int find2(int k) {
int l = 0, r = 5;
while(l < r) {
int mid = l + r + 1 >> 1;
if(a[mid] <= k) l = mid;
else r = mid - 1;
}
return l;
}
//返回第一个大于k的数的下标
int find3(int k) {
int l = 0, r = 5;
while(l < r) {
int mid = l + r >> 1;
if(a[mid] > k) r = mid;
else l = mid + 1;
}
return l;
}
//返回第一个大于等于k的数的下标
int find4(int k) {
int l = 0, r = 5;
while(l < r) {
int mid = l + r >> 1;
if(a[mid] >= k) r = mid;
else l = mid + 1;
}
return l;
}
int main() {
cout<<find1(5)<<endl; //输出2
cout<<find2(5)<<endl; //输出3
cout<<find3(5)<<endl; //输出4
cout<<find4(5)<<endl; //输出3
return 0;
}
总结:
- 若区间 [l, r] 分成左右两个区间,左区间满足条件,右区间不满足条件,答案是左区间的右端点,则 l = mid,且 mid = (l + r + 1) / 2
- 若区间 [l, r] 分成左右两个区间,右区间满足条件,左区间不满足条件,答案是右区间的左端点,则 r = mid,且 mid = (l + r) / 2
下一篇: 顺序查找和二分查找表