本文共 3079 字，大约阅读时间需要 10 分钟。

使用二分查找的前提；所查找的部分一定要具有单调性；

二分查找的理论； 折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较， 如果x=a[n/2]则找到x，算法终止。 如果x《a[n/2]，则我们只要在数组a的左半部继续搜索x，这里假设数组元素呈升序排列）。 如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。

1；二分查找之数组；

已知一个数组利用二分查找找到某个元素的下标；

#include
   
    int ef(int*a,int len, int t)//查找的函数{    int st = 0;    int end = len-1;    int mid ;     **while(st <= end){
  //跳出循环的条件        mid = (end -st)/2+st;//防止 (end +st)越界        if(a[mid] == t){
  //这个if结构是关键            return mid;        }        else if(a[mid] > t){            end = mid-1;        }        else st = mid+1;    }**     return -1;//没有找到这个元素}int main(){    int m;    int a[10]={
  1,2,3,4,5,6,7,8,9,10};    m = ef(a,10,8);//在数组a[10]中找元素8的位置；     printf("%d\n",m);    return 0 ;}
   

2；对函数二分查找；

就是解方程，保证精确度； HDOJ-2199 给出方程： 8*x4 + 7*x3 + 2*x2 + 3*x + 6 = Y 其中，实数Y满足 (fabs(Y) <= 1e10) 输入Y 请输出x在区间[0,100]的解，结果精确到小数点后4位。

#include
   
    double f(double x){    double y;    y = 8*x*x*x*x+7*x*x*x+2*x*x+3*x+6;    return y;}int main(){    int n;    double y,st,end, mid;    scanf("%d",&n);    while(n--){        scanf("%lf",&y);        if(f(0)<=y&&y<=f(100)){             st = 0;            end = 100;            while(end - st > 1e-7){
  //1e-7是精度问题；                 mid = (end-st)/2+st;                if(f(mid) > y){                    end = mid-1e-7;                }                else                    st = mid + 1e-7;            }                   printf("%.4lf\n",(end-st)/2+st);         }        else     printf("No solution!\n");    }     return 0 ;}
   

上面的1e-7次是保证精确度问题，一般取1e-7就好了；

3；二分查找对方程的导数二分查找；

HDOJ-2899 给出函数： F(x) = 6*x7 + 8*x6 + 7*x3 + 5*x2 - y*x 其中，实数y满足 (0

#include
   
    #include
    
     double y;double ds(double x)//导函数是单调递增的函数； {    return 42.0*pow(x,6.0)+48.0*pow(x,5.0)+21.0*pow(x,2.0)+10.0*x-y;} double hs(double x){    return 6.0*pow(x,7.0)+8.0*pow(x,6.0)+7.0*pow(x,3.0)+5.0*pow(x,2.0)-y*x;}int main(){    int n;    double st,end,mid;    scanf("%d",&n);    while(n--){        scanf("%lf",&y);        if(ds(100)<0){
  //导数的最大值都小于0则他就是最小值了             printf("%.4lf\n",hs(100));            continue;        }        if(ds(0)>0){            printf("%.4lf\n",hs(0));            continue;        }        st = 0;        end = 100;        while(end-st>1e-8){
  //这里的精度是？？？？？             mid = (end-st)/2+st;            if(ds(mid)<0){
  //导数小于0则说明最小值在中间到后面那部分                 st = mid;            }            else{                end = mid;            }        }        printf("%.4lf\n",hs(mid));    }    return 0 ;}
    
   

4；

4.1二分查找使用的关键在于； 被查找的一定要具有单调性； 4.2二分查找代码实现的关键在于 while条件和if判断与折中；

while(end-st>1e-8){
  //保证精确度一般取1e-7左右；            mid = (end-st)/2+st;            if(ds(mid)<0){
  //导数小于0则说明最小值在中间到后面那部分                 st = mid;            }            else{                end = mid;            }        }

while(end - st > 1e-7){
  //1e-7是精度问题；                 mid = (end-st)/2+st;                if(f(mid) > y){                    end = mid-1e-7;                }                else                    st = mid + 1e-7;            }

看几个样例应该有点感觉了吧；

转载地址：https://blog.csdn.net/zw1996/article/details/51878307 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！