Java中的二分-最大值最小值问题

前言

本章的二分查找并不是很详细，适合对二分查找有初步了解，缺乏例子和实战的同学，如果没学习过的话，可以先系统学习一下二分查找，更便于理解。二分查找的关键词是“最” “区间”（区间可能隐含再题意里）

二分查找的原理

所谓二分就是将一个长的数据分为两半，中间这个交界处就是我们要找的值，所以称之为二分，二分查找适合找最大值或最小值问题。首先，作为查找对象的必须是有序的，我们分别用两个指针（Java中用数组下标实现，C语言里可以用指针）：left和right，指向数组头和尾，然后用一个mid作为二者的中点，检查mid是否是符合条件，不符合的话，取mid左或者右区间（看实际情况），再执行上述操作。

二分查找代码实现

例子：在一个长为len的有序集合里，查找x元素

intleft=0,right=len;while(left<right){intmid=(left+right)/2;if(mid>x)left=mid+1;elseright=mid;}

例题1（FROM 蓝桥杯Java 2022 省赛 A 组 I 题）

思路

1.题中提到“最大边长”“尽可能大”，符合我们的二分查找关键词
2.二分查找我们先找起始边界，最少边长是1，所以 left=1，right 正常应该是：最长的边长，但是这里不好搜索（冗余），所以我们直接使用题中给出的边长上界——10^5 来作为right。
3.当下巧克力能切多少块？用 （长 / 猜测值）*（宽 / 猜测值）。再将所有巧克力的结果累和，就得出了：该猜测值可以切出多少块方形巧克力。

代码实现

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerinput=newScanner(System.in);intn=input.nextInt();intk=input.nextInt();int[]h=newint[n];int[]w=newint[n];for(inti=0;i<n;i++){h[i]=input.nextInt();w[i]=input.nextInt();}intleft=1,right=1e5;while(left<right){intmid=(left+right)/2;if(check(h,w,k,mid))//如果符合条件，我们再尝试着把边长加大left=mid+1;elseright=mid;//不符合条件，说明当前边长太大了，我们要缩小}System.out.print(left-1);//最后得出结果，为什么是left-1，后边有解答}staticbooleancheck(int[]h,int[]w,intk,intmid){intans=0;//累和的for(inti=0;i<h.length;i++)ans+=(h[i]/mid)*(w[i]/mid);//把当下取出的第i块巧克力算出能切多少块小的并累和if(ans>=k)//如果累和结果满足题意k块，返回真，回主函数中尝试加大边长returntrue;elsereturnfalse;}}

可能会有的疑问：

• 为什么最后使用的left-1而不是left？
  这和二分的逻辑有关，我写的代码left最后指向的是：该数组中，不符合题意的值的边界，指向的是不符合的那个，所以要减一，如果中间代码写成这样：那结果就是left——符合题的值的边界

while(left<=right){intmid=(left+right+1)/2;if(check(h,w,k,mid))//如果符合条件，我们再尝试着把边长加大left=mid+1;elseright=mid-1;//不符合条件，说明当前边长太大了，我们要缩小}

例题2（FROM 蓝桥杯Java 2018 省 B）

思路

本题是二分查找和前缀和的结合应用，如果对前缀和不了解的可以去看我昨天的《Java中的前缀和》
1.先考虑b和c数组，新建数组B[n]，其中B[i]储存的是：第i个b元素，可以取的c元素的个数。换而言之，就是有几个c元素比当下的b元素大。
2.触发二分查找关键词“区间”，于是我们取b[i]，再用二分查找的形式，找到大于该b[i]的区间边界，用边界下标算出这里应该储存的B[i]
3.再看a和b数组，这里运用了一个前缀和进行预处理，也就是，如果 b[i]>a[i]，那么有B[n]+B[n-1]+…+B[i]这么多个c大于b，该b又大于a（这里看代码更好理解）
4.注意：二分查找的一个条件就是有序，所以读入之后要先排序

代码实现

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerinput=newScanner(System.in);intn=input.nextInt();int[]a=newint[n];int[]b=newint[n];int[]c=newint[n];int[]B=newint[n];for(inti=0;i<n;i++)a[i]=input.nextInt();for(inti=0;i<n;i++)b[i]=input.nextInt();for(inti=0;i<n;i++)c[i]=input.nextInt();Arrays.sort(a);//排序Arrays.sort(b);Arrays.sort(c);for(inti=0;i<n;i++){intleft=0,right=n-1;while(left<right){//二分查找intmid=(left+right)/2;if(c[mid]>b[i])right=mid;elseleft=mid+1;}if(c[left]>b[i])B[i]=n-left;//left是边界，用总数n减去边界left就是有多少个c大于此时的b}longans=0;//开long防止溢出，累加器long[]sum=newlong[n+1];//前缀和，一般前缀和开的数组要比原数组大一个for(inti=1;i<=n;i++)sum[i]=sum[i-1]+B[i-1];//处理前缀和for(inti=0;i<n;i++){intleft=0,right=n-1;//数组末尾下标是n-1，如果写成n会超限报错while(left<right){intmid=(left+right)/2;if(b[mid]>a[i])right=mid;elseleft=mid+1;}if(b[left]>a[i])//同样是二分查找，找到此时a所对应的b的边界ans+=(sum[n]-sum[left]);//sum之间的差就是left到末尾n每个b对应的c的个数累和}System.out.print(ans);}}

可能会有的问题

• 为什么要有B数组？为什么要有sum数组？
  因为在构造abc的时候，即使是相同的c，但是b变了，还是一个新的组合，所以就算这些b所对应的那些c完全一样，也是要重新累和的。B中装的就是对应几个c，sum就是把这些B进行累和。
  

例题3 - double数组的二分（FROM 洛谷P1577）

触发关键词最长，思路就是最简单的二分，主要是学习double数组的二分
关键点

• double中不存在“==”
• 想知道两个double数是否“相等”，只能相减再与极小的数进行对比，如果比该数小，我们把它近似看作相等

代码实现

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannerinput=newScanner(System.in);intn=input.nextInt();intk=input.nextInt();double[]l=newdouble[n];for(inti=0;i<n;i++)l[i]=input.nextDouble();Arrays.sort(l);doubleleft=0,right=l[n-1];while(right-left>1e-2){doublemid=(left+right)/2;//double mid = (left+(right -left))/2;//如果数组字太大怕double超限，可以用这种方式写if(check(mid,k,l))left=mid;//double中mid是连续的，不需要进行加一减一的划分边界elseright=mid;}System.out.print(left);}staticbooleancheck(doublemid,intk,double[]l){intans=0;for(doubleL:l)ans+=(int)(L/mid);//求该绳子能切几段，并累和returnans>=k;}}