D.二分查找-二分答案-求最小——1283. 使结果不超过阈值的最小除数

题目链接：1283. 使结果不超过阈值的最小除数（中等）

算法原理：

解法：二分查找

6ms击败94.13%

时间复杂度O(n×log(max_num))

因为是找最小，在左边，因此选用最左端点模型

①题目没说一定升序，且除数一旦大于最大值，之后结果都是1，因此right要取数组中的最大值，需要O(N)时间复杂度的一次遍历

②分析要找的目标值，来分析left和right最终的位置，写出判断方法check，判断当前mid作为除数是否符合<=t的条件

③如果mid在最左端点的左边，那么left=mid+1，此时分析check方法，分析如上图，对应的值应该是false

④咱们要找的就是未知的符合条件的最左端点，所以left最终的位置即答案，无需分析第二落到的位置

⑤小细节：left初始化为1，因为当最左端点就是left落到的位置时，0不能做除数，除数最小也是1

Java代码：

class Solution { public int smallestDivisor(int[] nums, int t) { //除数不能是0，所以left初始化为1 int left=1,right=0; for(int x:nums) right=Math.max(x,right); //找除数最小：最左端点模型 while(left<right){ int mid=left+(right-left)/2; if(!check(nums,mid,t)) left=mid+1; else right=mid; } return left; } private boolean check(int[] nums,int mid,int t){ int sum=0; for(int x:nums){ //+mid-1：补足余数，完成向上取整 sum+=(x+mid-1)/mid; if(sum>t) return false; } return true; } }