【AcWing】1.1.3二分搜索

一、二分搜索

1、查找数的范围

• 原题链接
  
   这道题看似是二分搜索的题目，实则就是二分搜索。与一般的搜索不同的是，若查找元素重复，则分别返回重复元素的左端下标和右端下标，若不存在则返回“-1 -1。我们常用的二分搜索是返回的重复元素的左端下标，稍作修改，则可以返回右端元素下标。

#include<iostream>
#include<stdio.h>
using namespace std;
const int N = 1e5+10;
int a[N];//若存在重复元素，则返回左边界
int searchLeft(int q[],int l,int r,int x)
{while(l<r){int mid = l+r>>1;if(q[mid]<x){l = mid+1;}else{r = mid ;}}return l;
}
//若存在重复，则返回右边界
int searchRight(int q[],int l,int r,int x)
{while(l<r){int mid = (l+r+1)>>1;if(q[mid]<=x)l = mid;elser = mid-1;}return r;
}
int main()
{int n,m;cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];}while(m--){int num;cin>>num;//搜索左边界int pos1 = searchLeft(a,0,n-1,num);//搜索有边界if (a[pos1]!=num){cout<<"-1 -1"<<endl;}else{int pos2 = searchRight(a,0,n-1,num);cout<<pos1<<' '<<pos2<<endl;}}system("pause");return 0;
}

2、数的三次方根

• 原题链接
• 
   这道题可以用二分搜索的方法，来搜索一个数的三次方根的近似解。

#include<iostream>
using namespace std;
int main()
{double x,l = -100000.0,r = 100000.0;cin>>x;while(r-l>1e-8){double mid = (l+r)/2.0;if(mid*mid*mid< x){l = mid;}elser = mid;}printf("%.6f\n",r);return 0;
}