二分
二分查找算法，查找效率极高，时间复杂度为O(logN)。
二分搜索
1.查找某个数是否在数组中
public static boolean exist(int[]arr,int x) {
//二分查找 1.查找某个数是否在数组中
int l = 0,r = arr.length;
if(arr.length == 0 || arr == null) {
return false;
}
while(l <= r) {
int mid = (l+r) / 2;
if(arr[mid] == x) return true;
else if(arr[mid] < x) l = mid+1;
else r = mid - 1;
}
return false;
}2.寻找大于等于某个数的最左边位置
public static int exist(int x) {
//二分查找 2.查找大于等于某个数的最左边位置
int[] arr = {1,3,5,5,9};
int l = 0,r = arr.length;
int ans = -1;
while(l <= r) {
int mid = (l+r) / 2;
if(arr[mid] >= x) { //更新ans值，往左二分
ans = mid;
r = mid - 1;
}
else {
l = mid + 1; //不记答案，往右二分
}
}
return ans;
}3.寻找小于等于某个数的最左边位置
public static int exist(int[] arr,int x) {
//二分查找 3.查找小于等于某个数的最右边位置
int l = 0,r = arr.length;
int ans = -1;
while(l <= r) {
int mid = (l+r) / 2;
if(arr[mid] <= x) { //更新ans值，往右二分
ans = mid;
l = mid + 1;
}
else {
r = mid - 1; //不记答案，往左二分
}
}
return ans;
}4.二分查找不一定发生在有序数组上，例如寻找峰值问题。二分查找算法其本质要求是确定某一侧必有或必没有。
class Solution {
public int findPeakElement(int[] nums) {
int n = nums.length;
if(n == 1) return 0;
if(nums[0] > nums[1]) return 0;
if(nums[n - 1] > nums[n - 2]) return n-1;
int l = 1,r = n - 2,mid = 0,ans = -1;
while(l <= r) {
mid = l + ((r - l) >> 1);
if(nums[mid] < nums[mid - 1]) { //mid不是峰值点，且左侧一定有峰值点；或两侧都有峰值点。往左二分
r = mid - 1;
}else if(nums[mid + 1] > nums[mid]){//mid不是峰值点，且右侧一定有峰值点，往右二分
l = mid + 1;
}else {
ans = mid;
break;
}
}
return ans;
}
}二分答案法
思路
1、估计最终答案的范围。
2、分析给定条件与最终答案之间是否具有单调性
3、建立f()函数，当答案固定的时候，分析给定条件是否达标。
4、在最终答案可能的范围上重复二分搜索，每次使用f()函数判断，直到二分结束，找到最合适的答案。
经典题目
一、爱吃香蕉的珂珂
https://leetcode.cn/problems/koko-eating-bananas/
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int l = 1;//最小速度，即二分答案法的左边界
int r = 0;
for(int x : piles) {
r = Math.max(r, x); //r定义为数组中的最大值，即最大的速度，二分答案法的右边界
}
int ans = 0;
while(l <= r) {
int mid = (l+r) / 2;
if(f(piles,mid) <= h) {//达标
ans = mid;//记录答案
r = mid - 1;//往左二分，查看是否有符合f函数的更小值
}else {//不达标，说明速度过慢，需要提高速度，即往右二分
l = mid+ 1;
}
}
return ans;
}
public long f(int[] piles,int speed) {
long ans = 0;
for(int x : piles) {
ans += (x + speed - 1) / speed;//piles/speed向上取整
}
return ans;
}
}二、画匠问题
https://leetcode.cn/problems/split-array-largest-sum/submissions/
class Solution {
public int splitArray(int[] nums, int k) {
int l = 0;//二分左边界。
int r = 0;
for(int x :nums) {
r += x;//二分右边界，即整个数组的累加和。
}
int need;//给定一个数组，一个和，求出的组数，用于与题目所给的k比较，从而确定二分的方向。
int ans = 0;//最后要输出的最小的最大值。
while(l <= r) {
int mid = (l + r) / 2;
need = f(nums,mid);
if(need <= k) {//若小于等于k，则说明组数少了，随之得出本次二分中点的和大了，遂更新答案，向左二分，尝试更小的和。
ans = mid;
r = mid - 1;
}else {//若大于k,则说明组数多了,随之得出本次给定的二分中点的和小了,遂不更新答案,往右二分,尝试更大的直。
l = mid + 1;
}
}
return ans;//返回结果。
}
public static int f(int[] arr,int sum){
int parts = 1;//f函数要返回的组数，与上述的need对应
int tmp = 0;//划分过程中子数组的累加和
for(int x : arr){
if(x > sum){//若数组中出现一项数大于给定的和，则本数组无法划分，返回正无穷。
return Integer.MAX_VALUE;
}
if(tmp + x > sum) {//数组从0开始向后一位累加，若累加的和超过了给定的和，
parts++; //说明当下子数组已越值，需要将本数交给下一组划分，
tmp = x; //则将组数加一，将本数赋值给tmp，重新开始累加。
}else {
tmp += x;//若累加和未曾越值，继续累加，直到越值或循环结束。
}
}
return parts;//返回组数
}
}三、机器人跳跃问题
https://www.nowcoder.com/practice/7037a3d57bbd4336856b8e16a9cafd71
import java.util.*;
public class Main{
public static int findAns(int[] arr){
int l = 0;//二分左边界
int r = 0;
int ans = -1;
int max = 0;
for (int i = 1; i < arr.length; i++) {
r = Math.max(arr[i],r);//二分右边界，即数组中的最大值
}
max = r;//将数组中的最大距离存储下来，用于在f函数中防溢出使用
while(l <= r){
int mid = (l + r) / 2;
if(f(mid,arr,max)){//若此时mid所指的能量值可以走到终点，则记录答案，往左二分，查看是否还有满足条件的最小值。
ans = mid;
r = mid - 1;
}else{
l = mid + 1;//若无法到达终点，则说明能量值过少，需要往右二分，尝试更大的mid。
}
}
return ans;
}
public static boolean f(int mid,int[] arr,int max){
for(int i = 1;i < arr.length;i++){
if(mid >= arr[i]){
mid += mid-arr[i];//若能量值>=高度，则能量变为能量+能量与高度的差值
}else {
mid -= arr[i]-mid;//否则，若能量值<高度，则能量变为能量值-高度与能量的差值
}
if(mid >= max){//若上述步骤计算出的能量值已经高于了数字中最高距离，
return true;//则不需要再继续计算，因为此时的能量值已经足够走到终点了。
}
if(mid < 0){
return false;//若能量值小于0，则说明无法到达终点，退出循环。
}
}
return true;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] arr = new int[n+1];
for (int i = 1; i <= n; i++) {
arr[i] = scan.nextInt();
}
System.out.println(findAns(arr));
}
}
四、找出第k小的数对距离
https://leetcode.cn/problems/find-k-th-smallest-pair-distance/
class Solution {
public int smallestDistancePair(int[] nums, int k){
int l = 0;二分左边界
int r;
int ans = -1;
Arrays.sort(nums);
r = nums[nums.length-1] - nums[0];//二分右边界，即数组中最大的差值（最大值 - 最小值）
while(l <= r){
int mid = (l+r)/2;
if (f(mid,nums) >= k){//若此时mid所指的差值可以使得数组中有大于等于k个数对出现，则说明差值还可缩小，遂记录答案，向左二分。
ans =mid;
r = mid - 1;
}else {
l = mid + 1;//反之则说明差值过小，遂向右二分，查找尝试更大的mid。
}
}
return ans;
}
public static int f(int limit,int[] nums){//滑动窗口判定
int ans = 0;
for (int l = 0,r = 0; l < nums.length; l++) {//从0开始遍历原数组，寻找满足条件的数对
while (r+1 < nums.length && nums[r+1] - nums[l] <= limit){//通过简单的滑动窗口算法计算满足差值小于等于limit的数对个数，并记录在ans中。用于二分时比较。
r++;
}
ans += r-l;满足条件(<=limit)的数对个数
}
return ans;
}
}五、肖恩的乘法表
https://www.lanqiao.cn/problems/3404/learning/
import java.util.*;
public class Main{
public static long KNumber(long n,long m,long k){
long l = 1;
long r = n*m;
long ans = -1;
while (l <= r){
long mid = (l+r)/2;
if(f(n,m,mid,k)){
ans = mid;
r = mid - 1;
}else {
l = mid + 1;
}
}
return ans;
}
public static boolean f(long n,long m,long mid,long k){//统计数组中小于等于mid的数的个数，看其有没有k个
long cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += Math.min(m,mid/i);
}
return cnt >= k;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
long n = scan.nextLong(),m = scan.nextLong(),k = scan.nextLong();
System.out.println(KNumber(n,m,k));
scan.close();
}
}