二分查找总结
有许多人感觉二分很简单，我以前也是这样感觉的，但是随着做的题目越来越多越感觉二分其实不好掌握，我们所了解的只不过是一些明显的二分而已，有许多二分都是隐式的并不明显。
二分思想：
二分类似于猜数字游戏，每次都猜给定区间的中间值，但是前提条件是此序列已经排好序了。如果猜小了下一次就到右区间猜，如果猜大了，下次就到左区间猜这样逐渐逼近正确的结果。每次缩小一半的范围，因此二分的时间复杂度为 O( logn ) .
步入正题：
首先讲一个细节，就是在取中间值 mid 的时候，有许多人用的是： mid = ( rt + le ) / 2 ; (这里用 le 代表左区间，用 rt 代表右区间 , mid 代表中间值 ) 看似没什么但是如果所给数有可能两个数相加就超出了范围怎么办？？是不是就不是想要的结果了 , so ~ > 要用：mid = le + ( rt - le ) / 2 ; 在判断结束条件的时候，有的人喜欢用 le < rt ( 左闭右开 ) 来判断， 有的人喜欢用 le <= rt ( 左闭右闭 ) 来判断，两种都可以只是循环修改条件的时候也要对应着修改。
一、单纯查找某个值是否存在。
左闭右闭区间：
-
int binary_search(int le ,int rt ,int m)
-
{
-
int mid ;
-
while(le <= rt)
-
{
-
mid = rt + (rt - le)/2 ;
-
if(a[mid] == m)
-
return mdi ;
-
else if(a[mid] > m)
-
rt = mid -1 ;
-
else le = mid + 1 ;
-
}
-
return -1 ; // 查找不成功
-
}
-
int binary_search(int le ,int rt ,int m)
-
{
-
int mid ;
-
while(le < rt)
-
{
-
mid = rt + (rt - le)/2 ;
-
if(a[mid] == m)
-
return mdi ;
-
else if(a[mid] > m)
-
rt = mid ;
-
else le = mid + 1 ;
-
}
-
return -1 ; // 查找不成功
-
}
二、查找某个值所在的区间
a [ mid ] = m ： 至少已经找到一个，而左边可能还有，因此区间变为 [ mid + 1 , rt ] ;
a[ mi ] > m ： 所求位置不可能在后面，但有可能是 mid ,因此区间变为 [ x , mid ] ;
a[mid ] < m ： mid 和前面都不可行，因此区间变为[mid+1 ,rt ] ;
查出的区间是 [ x , y )
查找最左边的下标: 此代码同---> lower_bound ( g , g + n , m ) - g ;
-
int binary_searchle(int le ,int rt ,int m)
-
{
-
int mid ;
-
while(le < rt)
-
{
-
mid = le + (rt-le)/2 ;
-
if(g[mid] >= m) rt = mid ;
-
else le = mid + 1 ;
-
}
-
return le ;
-
}
-
int binary_searchrt(int le ,int rt ,int m)
-
{
-
int mid ;
-
while(le < rt)
-
{
-
mid = le + (rt-le)/2 ;
-
if(g[mid] <= m) le = mid+1 ;
-
else rt = mid ;
-
}
-
return le ;
-
}
做题感悟：
比赛时看到这看到这题真是悲喜交加，喜的是以前做过类似的两道题，悲的是忘的差不多了，题目中还出现了 sin ( x ) ,cos( x ),e^( -x ) ,真是让我不知如何是好
.从中可以看出掌握知识不牢固，没有真正领会二分的精髓。其实在做第四题做超过半个小时时就应该切入这题至少有做出来的可能（当时为什么没切题呢？？？）。所以以后掌握知识一定要牢固，掌握其精髓。下面借着这个题来总结一下这类的题。
判断单调性：
首先这种题一般需要判断函数的单调性（不是递增就是递减）。（1）判断单调性一般用求导数来解决。假如给你区间（a , b），如果 f ( x ) 的导数在（a ，b）内小于零则 f(x)在此区间内单调递减，如果 f( x ) 的导数在区间（a，b）内大于零则f( x ) 在此区间内单调递增。（2）如果函数内的每个函数都是单调递增（递减）则函数整体为单调递增（递减）。（3）可以在区间内选择两个数代入方程内观察单调性。
二分控制精度：
因为已经知道单调性直接二分即可，尽量精度调节大一点。
解题思路（本题）：做这道题有学会了几个数学函数先总结一下：exp（）函数：用来计算以e为底的 x 次方值，然后将结果返回（e=2.71828 18284）。sin（x），cos（x），tan（x）( x 必须是弧度谨记)，可以直接用。因为此函数中每一个函数都是递减的，所以整个函数都是递减的（精度尽量大一点）。
代码：
-
#include<stdio.h>
-
#include<math.h>
-
double p,q,r,s,t,u ;
-
double find(double x) // 方程
-
{
-
return p*exp(-x)+q*sin(x)+r*cos(x)+s*tan(x)+t*x*x+u ;
-
}
-
double binary_search(double le,double rt) //二分
-
{
-
double mid,temp ;
-
while(le<=rt)
-
{
-
mid=le+(rt-le)/2.0 ;
-
temp=find(mid) ;
-
if(fabs(temp)<=0.000001)
-
return mid ;
-
else
-
temp > 0 ? le=mid : rt=mid ;
-
}
-
return -1 ;
-
}
-
int main()
-
{
-
while(scanf("%lf%lf%lf%lf%lf%lf",&p,&q,&r,&s,&t,&u)!=EOF)
-
{
-
if(find(0)<0||find(1)>0) // 可以换为find（0）*find（1）>0
-
printf("No solution\n") ;
-
else
-
printf("%.4lf\n",binary_search(0,1)) ;
-
}
-
return 0 ;
-
}
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/18219595
- 点赞
- 收藏
- 关注作者
评论（0）