NYOJ 776 删除元素（二分查找）

题目链接~~>

做题感悟： 做了这题后觉悟了很多，才认识到二分的强大，以前只是对二分有点了解，今天才真正明白二分。首先是如果你没读懂题意，做再多遍也是 WA 。其次是当你做一个题一直 WA 时你就应该考虑一下是否没读懂题意，是否该用 long long 的没用 long long 等。不要不管三七二十一狂提交！

二分查找（以下情况为查找左闭右开区间）：复杂度 log（n）

              (1)、单纯查找一个数是否在一个序列里。

代码：

  

   

    

     

    
    

     

      int binary(int x,int y,int v)// 查找左闭右开区间
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int m ;
     
    
   

    

     

    
    

     
 while(x<y) // 这里要和上面保持一致
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       m=x+(y-x)/2 ;
     
    
   

    

     

    
    

     
 if(g[m]==v)  return m ;
     
    
   

    

     

    
    

     
 else if(g[m]>v)  y=m ; 
     
    
   

    

     

    
    

     
 else   x=m+1 ; 
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return -1 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

            (2)、二分查找求下界。返回的时候返回的是大于等于要查找的值的下标！

代码：

  

   

    

     

    
    

     

      int lower_bound(int x,int y,int v)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int m ;
     
    
   

    

     

    
    

     
 while(x<y)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       m=x+(y-x)/2 ;
     
    
   

    

     

    
    

     
 if(g[m]>=v)  y=m ;
     
    
   

    

     

    
    

     
 else   x=m+1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return x ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

             (3)、二分查找求上界。返回的时候返回的是大于要查找的值的下标（如果要查找的值是最大值返回数组个数）。

            (4)、求下界只需要把   if ( g[m] >= v)  y=m ;   else   x=m+1 ; 改为if ( g[m] <= v)  x=m+1 ;  else   y=m+1 ;

            (5)、用函数求上界和下界。头文件：#include<algorithm>+using namespace std ;

            求下界函数：lower_bound(数组名，数组名+数组元素个数，要查找的数)-数组名（因为返回的是地址） ；

            求上界函数：upper_bound(数组名，数组名+数组元素个数，要查找的数)-数组名（同上） ；

本题代码：

  

   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      int n ;
     
    
   

    

     

    
    

     

      int g[100005] ;
     
    
   

    

     

    
    

     

      int binary(int x,int y,int v) // 二分查找求上界
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int m ;
     
    
   

    

     

    
    

     
 while(x<y)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       m=x+(y-x)/2 ;
     
    
   

    

     

    
    

     
 if(g[m]<=v)   x=m+1 ;
     
    
   

    

     

    
    

     
 else y=m ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return n-x ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i ;
     
    
   

    

     

    
    

     
 while(scanf("%d",&n)!=EOF)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     
 scanf("%d",&g[i]) ;
     
    
   

    

     

    
    

     

       sort(g,g+n) ;
     
    
   

    

     

    
    

     
 int ans=1999999999,num ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       num=binary(0,n,g[i]*2)+i ;
     
    
   

    

     

    
    

     

       ans= ans < num ? ans : num ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%d\n",ans) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
  
 

关于二分的博客~~>
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/14554441