二段性
当给定一个条件时，两边呈现出有且仅有的两种状态。
整数二分
板子：
单调递增序列a中查找>=x的数中最小的一个(x或x的后继)
public int bsearch_1(int l,int r){
while (l < r){
int mid = l + r >> 1;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}单调递增序列a中查找<=x的数中最大的一个(x或x的前驱)
public int bsearch_2(int l,int r){
while (l < r){
int mid = l + r + 1 >> 1;
if (a[mid] <= x) l = mid;
else r = mid - 1;
}
return l;
}若bsearch_2中也采用 mid = l + r >> 1
当r - l 等于1时，就有mid = l + r >> 1 = l，进入l = mid分支会造成死循环，若进入r = mid - 1分支会造成l > r，循环不能以l = r结束。
无解情况
mid = (l + r) >> 1不会取到r这个值，mid = (l + r + 1) >> 1不会取到l这个值。可以利用这个性质来处理无解情况，把最初二分区间[1，n]分别扩大为[1，n + 1]和[0，n]，把a数组的一个越界下标包含进来，如果最后二分终止于扩大后的这个越界下标上，则说明a中不存在所求的数。
实数域二分
板子：
public double bsearch_3(double l ,double r){
double eps = 1e-6;
while (r - l > eps){
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}例题：
整数二分：
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回
-1 -1。输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回
-1 -1。数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000输入样例：
6 3 1 2 2 3 3 4 3 4 5输出样例：
3 4 5 5 -1 -1
import java.util.Scanner;
public class Demo01 {
static int N = (int)1e5 + 10;
static int n,m;
static int q[] = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < n; i++) {
q[i] = sc.nextInt();
}
while (m -- > 0){
int v = sc.nextInt();
int l = 0;
int r = n - 1;
while (l < r){
int mid = l + r >> 1;
if (q[mid] >= v) r = mid;
else l = mid + 1;
}
int left = l;
if (q[l] != v){
System.out.println(-1 + " " + -1);
continue;
}
l = 0;
r = n;
while (l < r){
int mid = l + r >> 1;
if (q[mid] > v) r = mid;
else l = mid + 1;
}
System.out.println(left + " " + (l - 1));
}
sc.close();
}
}浮点数二分：
给定一个浮点数 n，求它的三次方根。
输入格式
共一行，包含一个浮点数 n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6 位小数。
数据范围
−10000≤n≤10000
输入样例：
1000.00输出样例：
10.000000
import java.util.Scanner;
public class Demo02 {
static double eps = 1e-8;
static double n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextDouble();
double l = -10000;
double r = 10000;
while (r - l > eps){
double mid = (l + r) / 2;
if (mid * mid * mid < n) l = mid;
else r = mid;
}
System.out.printf("%.6f",l);
sc.close();
}
}