3-二分

算法思想

1. 划分区间
   1. 根据数值大小划分为两个区间
2. 递归处理目标区间
3. 注意事项
   • 无论待查找值 x 是否在集合 q 当中，经查找后均会得到一个查找结果

记忆口诀

1. 男左女右；下头男，上头女
   1. 左边界向下取整，右边界向上取整

算法模板

boolean check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
// 例如，寻找左边界 
int bsearch_1(int l, int r)  
{  
    while (l < r){
		int mid = l + r >> 1;   //向下取整  
        if (check(mid)) r = mid;    // check()判断mid是否满足性质  
        else l = mid + 1;    
    }    
	return l;
}  
  
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：  
// 例如，寻找右边界  
int bsearch_2(int l, int r)  
{  
    while (l < r){        
	    int mid = l + r + 1 >> 1;
	    if (check(mid)) l = mid;        
	    else r = mid - 1;    
	}   
	return l;
}