做题感悟： 做了这题后觉悟了很多，才认识到二分的强大，以前只是对二分有点了解，今天才真正明白二分
。首先是如果你没读懂题意，做再多遍也是 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 ;
}