一、算法模板

（1）整数二分

整数二分有两套算法模板，这两套算法模板几乎涵盖了所有二分算法的题目。

它们的主要区别在于①和②处对 mid 的赋值不同，相应的，右边界 r 与左边界 l 的值的更新也就不同。二分首先要做的是确定边界，整数二分的本质在于边界的判断。每次都必须选择答案所在的区间进行处理。

在运用下面两套模板时，先不要管细节；找到题干中要求的性质的边界后，先套上模板即可；然后再对边界点作出考虑：如果 check() 的值为 true，边界点包括不包括在目标区间内？根据这个问题的结果，填充：

if(check()) {...    //填充
}else{...    //填充
}

再根据实际填充的结果，对应到下面的模板，确定 mid 的赋值处是否要加一。

// 检查x是否满足某种性质
boolean check(int 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;
}

（2）浮点数二分

浮点数二分与整数二分的逻辑是相同的。不过，由于浮点数的除法结果是浮点数，因此不存在边界问题，相对来说更加简单，也不用考虑mid取值加一减一的问题。

二、例题

例题：acwing-789.数的范围

解析：

这道题直接暴力是会超时的，最好的方法就是二分求解。

如果要查找起始点：

由上面的分析过程和代码模板可得如下代码：

// 二分找开始点
int l = 0, r = n-1;
while(l < r) {int mid = (l+r) >> 1;if(array[mid] >= k) {r = mid;}else{l = mid + 1;}
}

因为下面的步骤是 r = mid 和 l = mid + 1，所以， mid 的赋值即为 (l+r) >> 1，不用再更改为 (l+r+1) >> 1 。

然后二分查找终点：

因此，得出查找终点的代码如下：

// 二分找结束点
l = 0;
r = n-1;
while(l < r) {int mid = (l+r+1) >> 1;if(array[mid] <= k) {l = mid;}else{r = mid - 1;}
}

题干可能不一定有解，但是二分的模板是一定有解的。二分后，通过性质，我们可以自行判断出无解的情况是什么。本题中，二分代码结束后 l 于 r 一定是相等的。此时，若 k 不等于 array[l]，那么说明要查找的数不存在。

结合题干要求的输入输出格式，补充完整代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner reader = new Scanner(System.in);int n = reader.nextInt();   //数组长度int q = reader.nextInt();   //询问个数int[] array = new int[n];for (int i = 0; i < array.length; i++) {array[i] = reader.nextInt();}while(q != 0) {q--;int k = reader.nextInt();   //要查询的元素// 二分找开始点int l = 0, r = n-1;while(l < r) {int mid = (l+r) >> 1;if(array[mid] >= k) {r = mid;}else{l = mid + 1;}}//没找到if(array[l] != k) {System.out.println("-1 -1");}else {System.out.print(l + " ");// 二分找结束点l = 0;r = n-1;while(l < r) {int mid = (l+r+1) >> 1;if(array[mid] <= k) {l = mid;}else{r = mid - 1;}}System.out.println(l);}}reader.close();}
}

例题：数的平方根

用浮点数二分的方法，求输入一个数 x 的平方根。结果保留6位小数。

由此，可以得出代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner reader = new Scanner(System.in);double x = reader.nextDouble();double l = 0, r = x;while(r - l >= 1e-8) {double mid = (l+r)/2;if(mid * mid >= x) {r = mid;}else{l = mid;}}System.out.printf("%.6f", l);reader.close();}
}

注意，若题干要求结果保留6位小数，精度就设为1e-8，若题干要求保留4位小数，精度就设为1e-6

要求保留几位小数，就把精度设置的比要求的大 2 位。

例题：acwing-790.数的三次方根

首先我们要识别出，这道题可用浮点数的二分来解。

二分首先要确定边界，该题中，可以直接将数的区间范围确定为 -10000~10000。与求平方根同理：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner reader = new Scanner(System.in);double n = reader.nextDouble();double l = -10000, r = 10000;while(r - l >= 1e-8) {double mid = (l+r)/2;if (mid * mid * mid >= n) {r = mid;} else {l = mid;}}System.out.printf("%.6f", l);reader.close();}
}

数的立方根同题也在蓝桥杯中考过：蓝桥-解立方根