个人倾向第一种 ;
可行区域在左侧 : 查找最后一个<=q的数的下标 :
- int find(int q){// 查找最后一个 <= q 的下标
- int l = 0 , r = n + 1 ;
- while(l + 1 < r){
- int mid = l + r >> 1 ;
- if(a[mid]<=q) l = mid ;
- else r = mid ;
- }
- return l ;
- }
可行区域在右侧 : 查找第一个>=q的数的下标 :
- int find(int q){ // 查找第一个>=q的下标
- int l = 0 , r = n + 1 ;
- while(l + 1 < r){
- int mid = l + r >> 1 ;
- if(a[mid]>=q) r = mid ;
- else l = mid ;
- }
- return r;
- }
- double find(double l, double r){
- const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
- while (r - l > eps)
- {
- double mid = (l + r) / 2;
- if (check(mid)) r = mid;
- else l = mid;
- }
- return l;
- }
以求一个浮点数(-10000 <= y <= 10000) 的三次方根 为例:
- double find(double y){ // 最大化查找
- double l = -100 , r = 100 ;
- while(r-l>1e-5){
- double mid = (l + r) / 2 ;
- if(mid * mid * mid <= y) l = mid;
- else r = mid ;
- }
- return l ;
- }
最小化查找 :
- class Solution {
- public:
- int searchInsert(vector<int>& nums, int target) {
- // 第一个 >= target 的下标
- int n = nums.size() ;
- int l = -1 , r = n ;
- while(l + 1 < r){// l + 1 == n 结束
- int mid = l + r >> 1 ;
- if(nums[mid]>=target) r = mid ;
- else l = mid ;
- }
- // nums[r] ;
- return r ;
- }
- };
最小化查找 :
- #include
- using namespace std ;
- const int N = 1e6 + 10 ;
- int a[N] ;
- int main(){
- int n , m ; cin >> n >> m ;
- for(int i=1;i<=n;i++) cin >> a[i] ;
- while(m--){
- int q ; cin >> q ;
- int l = 0 , r = n + 1 ;
- while(l + 1 < r){
- int mid = l + r >> 1 ;
- if(a[mid] >= q) r = mid ;
- else l = mid ;
- }
- if(a[r]==q) cout << r << " " ;
- else cout << -1 << " " ;
- }
- }
浮点数二分 :
- #include
- using namespace std ;
- const int N = 1e6 + 10 ;
-
- double a , b , c , d ;
-
- double f(double x){
- return a * x * x * x + b * x * x + c * x + d ;
- }
-
-
- double find(double l , double r){
- while(r-l>0.0001){
- double mid = (l + r) / 2 ;
- if(f(mid) * f(r) < 0) l = mid ;
- else r = mid ;
- }
- return l ;
- }
-
- int main(){
- cin >> a >> b >> c >> d ;
- for(int i=-100;i<100;i++){
- double y1 = f(i) , y2 = f(i + 1) ;
- if(!y1) printf("%.2f ",1.0 * i) ;
- if(y1 * y2 < 0){
- printf("%.2f " , find(i , i + 1)) ;
- }
- }
- }