现在的位置: 首页 > 综合 > 正文

njupt 1163 活动安排问题 从中看到的二分问题 二分模版

2013年10月06日 ⁄ 综合 ⁄ 共 798字 ⁄ 字号 评论关闭

http://blog.csdn.net/yangshuolll/article/details/8040534

从 南京邮电这道题中折射出自己二分问题的不足

自己就很少研究二分这类算法的模版   没有形成一个固定的模板  当自己码了好多二分查找的问题好 在众多的模版中 找到了个最稳定的模版

直接贴代码  :      在10个数中 查找 确定的数

二分稳定模版

这里一定要加( middle=(l+r)/2  ) 要注意逻辑运算符的运算顺序要大于 赋值运算符 

int a[n];
while(scanf("%d",&find))
{
      l=0;
      r=n+1;
     while(    (middle=(l+r)/2 )  &&  l+1<r)    //这里一定要加( middle=(l+r)/2  ) 要注意逻辑运算符的运算顺序要大于 赋值运算符 
     {
             if( a[middle]>find  )   r=middle;
             else l=middle;
     }
    printf( "%d",a[middle]);   
}

测试样例:

#include<stdio.h>
int a[10]={0,1,2,5,6,7,8,13,15,17};
int main()
{
   int l,r,middle;
   int find;
   while(scanf("%d",&find))
   {
       l=0; 
       r=10;  //这里右边界r要特别的注意数组存到了第9位 但是 r应当比9位多一位 扩展到10 否则查找不到17这右边界上的结果
      while( ( middle=(l+r)/2 ) && l+1<r)
      {
         printf("l=%d m=%d r=%d\n",l,middle,r);             
         if( a[middle]>find )r=middle;
         else  l=middle;            
      }    
    printf("l=%d m=%d r=%d\n",l,middle,r);
    printf("%d %d %d\n",a[l],a[middle],a[r]); //middle 就是要找的位数 其中如果找不到要找的值 输出的是最靠近find的最大值。
  
  } 
}

抱歉!评论已关闭.