整数二分步骤
找一个区间[L,R],使得答案一定在该区间中
找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段行的分界点
分析arr[Mid]在该判断条件下是否成立，如果成立，考虑答案在哪个区间；如果不成立，考虑答案在哪个区间
如果更新方式是R=Mid,则不用做任何处理；如果更新方式是L=Mid，则需要在计算Mid是加上1
数的范围
原题链接
题解思路：
该题其实就是一道模板题，按照整数二分的步骤即可解出结果。
数组按序排列，相同数字排列在一起，所有该题所求即为一段x的左右端点，二分输出其两个端点即可。
代码实现：
import java.util.*; public class Main { final static int N=100010; static int []arr=new int[N]; static int n,q; public static void main(String[]args) { Scanner sca=new Scanner(System.in); n=sca.nextInt(); q=sca.nextInt(); for(int i=0;i<n;i++) arr[i]=sca.nextInt(); for(int i=0;i<q;i++) { int x=sca.nextInt(); //二分x的左端点 int l=0,r=n-1; //确定区间范围 while(l<r) { int mid=l+r>>1; if(arr[mid]>=x) r=mid; else l=mid+1; } if(arr[l]==x) { System.out.print(l+" "); r=n-1; //二分x的右端点 //因为前边已经确定了x的左端点，所以二分范围可以从l开始到n while(l<r) { int mid=l+r+1>>1; if(arr[mid]<=x) l=mid; else r=mid-1; } System.out.println(l); }else { System.out.println(-1+" "+-1); } } } }
实数二分步骤
细节（只有第四步）与整数二分不同，实数是连续而整数是离散的，所以求mid时一定会取得中间值。
其他步骤与整数二分相同。
数的三次方根
原题链接
题解思路：
1.确定区间：
因为−10000≤n≤10000，所以[L,R]为[-10000,10000].
2.给出判断条件：
midmidmid>=n
3.根据判断情况，确定答案落在哪个区间
4.更新区间范围：
L=mid或者R=mid
代码实现：
import java.util.*; public class Main { static double n; public static void main(String[]args) { Scanner sca=new Scanner(System.in); n=sca.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); } }
1.四平方和
原题链接
题解思路：
这道题我们首先想到的是通过暴力循环来求解，分别枚举a,b,c然后求出d即可，但是我们分析时间复杂度，数据范围为5000000，所以每层循环大约次数为2300次，三次循环其时间复杂度将会非常大，所以我们必须通过其他方法来完成。
在一堆数据中寻找符合条件的一组数据，可以通过二分或者哈希两种方法来做（注意：如果通过数组二分也会超时，所以我们把数据存在ArrayList中以减少时间）
代码实现1（链表+二分）：
该方法需要注意的是字典序问题，所以需要在list.sort（）时用比较器，依次将平方和、c、d的顺序来排序。
import java.util.*; public class Main { static ArrayList<int[]> list = new ArrayList<>(); public static void main(String[] args) { Scanner sca = new Scanner(System.in); int n = sca.nextInt(); for (int c = 0; c * c <= n; c++) { for (int d = c; c * c + d * d <= n; d++) { int t = c * c + d * d; list.add(new int[]{c, d, t}); } } list.sort(new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { if (o1[2] != o2[2]) return Integer.compare(o1[2], o2[2]); if (o1[0] != o2[0]) return Integer.compare(o1[0], o2[0]); return Integer.compare(o1[1], o2[1]); } }); for (int a = 0; a * a <= n; a++) { for (int b = a; a * a + b * b <= n; b++) { int x = n - a * a - b * b; int l = 0, r = list.size() - 1; while (l < r) { int mid = l + r >> 1; if (list.get(mid)[2] >= x) r = mid; else l = mid + 1; } if (list.get(l)[2] == x) { System.out.println(a + " " + b + " " + list.get(l)[0] + " " + list.get(l)[1]); return; } } } } }
代码实现2（手动实现哈希表）：（手动实现的方法比直接使用哈希表速度快一倍）
（手动实现哈希表就是通过设置两个数组实现一一对应的关系）
哈希表就是一一对应的关系，我们通过升序循环，把第一次出现的平方和所用的c、d存储到数组中，就不用再自行进行排序。
import java.util.Scanner; public class Main1 { final static int N=5000010; static boolean[]st=new boolean[N]; static PII[]p=new PII[N]; public static void main(String[] args) { Scanner sca=new Scanner(System.in); int n= sca.nextInt(); for(int c=0;c*c<=n;c++) { for(int d=c;c*c+d*d<=n;d++) { int t=c*c+d*d; if(!st[t]) { st[t]=true; p[t]=new PII(c,d); } } } for(int a=0;a*a<=n;a++) { for(int b=a;a*a+b*b<=n;b++) { int x=n-a*a-b*b; if(st[x]) { System.out.print(a+" "+b+" "+p[x].c+" "+p[x].d); return; } } } } } class PII { int c; int d; public PII(int c, int d) { this.c = c; this.d = d; } }
代码实现3（哈希表）：
import java.util.*; public class Main2 { static HashMap<Integer,int[]>map=new HashMap<>(); public static void main(String[] args) { Scanner sca=new Scanner(System.in); int n=sca.nextInt(); for(int c=0;c*c<=n;c++) { for(int d=c;c*c+d*d<=n;d++) { Integer t=c*c+d*d; if(map.get(t)==null) { map.put(t,new int[]{c,d}); } } } for(int a=0;a*a<=n;a++) { for(int b=a;a*a+b*b<=n;b++) { Integer x=n-a*a-b*b; if(map.get(x)!=null) { System.out.println(a+" "+b+" "+map.get(x)[0]+" "+map.get(x)[1]); return; } } } } }
2.机器人跳跃问题
原题链接
题解思路：
这道题我们分析题意可得，每次跳到下一台阶都有可能发生能量变化，但是都是e新=2e-h，我们给定能量区间进行二分，对mid的能量进行判断，如果跳到最后一个台阶且e>=0说明这个初始能量值符合要求。
代码实现：
import java.util.*; public class Main { final static int N=100010; static int[]arr=new int[N]; static int n; public static void main(String[]args) { Scanner sca=new Scanner(System.in); n=sca.nextInt(); for(int i=0;i<n;i++) { arr[i]=sca.nextInt(); } int l = 0, r = 100000; while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } System.out.print(l); } public static boolean check(int e) { for(int i=0;i<n;i++) { e=2*e-arr[i]; if(e>=1e5)return true; /*如果能量大于最大高度，则后边能量值的变化将为单调递增， 肯定大于0，所以直接返回true即可*/ if(e<0)return false; } return true; } }
3.分巧克力
原题链接
题解思路：
每块巧克力可以分成的小块数等于（h/a）*（w/a） h、w分别为长宽，a为小块巧克力边长，随着边长的增大，可分成的小巧克力块数减少，所以二分边长，判断条件为是否块数大于等于k，如果满足，再把mid调大。
代码实现：
import java.util.*; public class Main { final static int N=100010; static int[]h=new int[N]; static int[]w=new int[N]; static int n,k; public static void main(String[]args) { Scanner sca=new Scanner(System.in); n=sca.nextInt(); k=sca.nextInt(); for(int i=0;i<n;i++) { h[i]=sca.nextInt(); w[i]=sca.nextInt(); } int l=1,r=100000; while(l<r) { int mid=l+r+1>>1; if(check(mid))l=mid; else r=mid-1; } System.out.print(l); } public static boolean check(int a) { int res=0; for(int i=0;i<n;i++) { res+=(h[i]/a)*(w[i]/a); if(res>=k)return true; } return false; } }
