二分查找两种情况

1：查找小于等于x的第一个元素

int min_x(int x){//查找不小于x的第一个元素 
    int l=0,r=n-1;
    while(l>1;
        if(a[mid] 
当a[mid] 
当a[mid]>=x时，其右边的元素也一定>=x，我们要找<=x的第一个位置，所以把右边消掉，保留mid；
 
2：查找大于等于x的第一个元素
 
int max_x(int x){//查找不大于x的第一个元素 
    int l=0,r=n-1;
    while(l>1;//避免死循环 
        if(a[mid]>x) r=mid-1;
        else l=mid;
	//由于l+r>>1是向下取整，所以上面不加1有可能这一步死循环 
    }
    if(a[l]==x) return l;
    else return -1;
}
 
当a[mid]>x时，其右边的数一定>x，所以消掉右边；
 
a[mid]<=x时，其左边的书一定<=x，把mid左边消掉，保留mid；
 
我们找>=x的第一个元素，由于>>运算符向下取整，mid=l+r>>1，只会取到l，所以如果a[mid]一直 <=l，会陷入死循环；mid应该=l+r+1>>1
 
 输入样例：
 
1 2 2 3 3 4
 
输出样例：
 
3 4
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5636302.html