一、二分搜索
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;
}