分治算法-----二分求最大最小

例题1:给n个实数,求它们之中最大值和最小值,要求比较次数尽量小。

思路:用递归调用函数,在函数里做出以下判断:

1 若left==right(只有一个数) max和min都为这个数

2 若left==right-1(只有两个数) max为较大的,min为较小的

3 除以上两种以外 首先定义中间值d,在递归调用left到d与d+1到right的函数,max为两函数返回值的最大值,min为最小值

核心思路如上

原代码:

 

       

错误原因:思路没错,但11行的if前面没有else,导致15行的else只建立在11行的if上,与思路不符,把if前面填个else即可:

     没有考虑到第11行如果没有else,那样15行的else只对应着11行的if,而与7行的if没有关系,而当right1==left1时,right1不等于left1加1,所以当left1==right1时,15行判断没有错误,照样运行,与思路相悖;

 经验教训:

      在今后使用if..else进行判断时,尽量用if..if ..if 来代替(当然漏掉的可能性会增加),争取不重复,不漏掉.

原文地址:https://www.cnblogs.com/jr-ag/p/8666325.html