常见算法题分类总结之二分算法(Binary-Search)：致敬经典，超越经典

前置知识

本文说的二分着重指的是二分答案

什么是二分

什么是二分答案？

答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小。
判断：根据题意写个check函数，如果满足check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间）。一直往复，直至到最终的答案。

这不就相当于高中做选择题的时候，完了，不会做，那咋搞，把四个选项代进去看看对不对吧！哪个行得通那个就是答案！！

只不过我们现在要找的是最大的或者最小的答案。

如何判断一个题是不是用二分答案做的呢?

1、答案在一个区间内（一般情况下，区间会很大，暴力超时）
2、直接搜索不好搜，但是容易判断一个答案可行不可行
3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。

此外，可能还会有一个典型的特征：求…最大值的最小 、 求…最小值的最大。

1、求…最大值的最小，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来
2、同样，求…最小值的最大时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走

算法思想：要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字

另外大家还是对二分的边界判断不太清楚的话强烈推荐二分算法详解大佬的这篇博客！！！

JDK自带的二分

	/*
	 * JDK自带的的二分查找方法，查找到关键字则返回关键字所在的数组下标位置，找不到该关键字就返回一个与最后查找位置相关的负数
	 */
	public static int binarySearchJDK(int[] arr,int value) {
		// jdk本身自带的二分查找
		int min =0;
		int max = arr.length-1;		
		while(min<=max){
			//采用无符号右移一位，即可以表示除以2
			int mid = (min+max)>>>1;
			int midValue = arr[mid];
			if(midValue>value){
				max = mid-1;
			}else if(arr[mid]<value){
				min = mid+1;
			}else{
				return mid;
			}			
		}
		//没有找到就返回一个与最终位置有关的负数
		return -(min+1);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

大家想进一步好好感受二分那就来看看下面的这些经典试题吧

经典题目

两数之和

/**
 * 两数之和
 * @Description: 找出nums中和为target的下标数组
 * @author: William
 * @date: 2022-06-17
 */
public class Num1 {
	//哈希方法
	public int[] twoSum(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<>();
		for(int i = 0; i < nums.length; i++) {
			if(map.containsKey(target - nums[i])) {//有就返回
				return new int[] {map.get(target - nums[i]), i};
			}
			map.put(nums[i], i);//没有就把下标和值的映射关系加进去
		}
		return new int[0];//说明没找到
	}
	
	//首先复制数组，用来寻找排序后的原坐标
	//然后对数组进行排序，用二分法判断两个元素的和与目标值的关系，如果目标值比和小，我们就移动右指针，
	//反之移动左指针，直到找到目标元素或两个指针相遇
	//然后我们判断下是否找到两个元素，如果找到了，我们判断下这两个元素是否相同，如果不同就通过find方法寻找原坐标
	//相同的就先找到一个元素 再分区找另外一个元素
	public int[] twoSum1(int[] nums, int target) {
		int[] cp = Arrays.copyOf(nums, nums.length);//为了记录下标
		Arrays.sort(cp);//排序
		int L = 0, R = cp.length - 1;
		while(L != R) {
			if(cp[L] + cp[R] == target) {
				break;//找到了
			}else if(cp[L] + cp[R] < target) {
				L++;
			}else {
				R--;
			}
		}
		if(L != R) {
			if(cp[L] != cp[R]) {//找到的情况
				return new int[] {find(nums, 0, nums.length, cp[L]), find(nums, 0, nums.length, cp[R])};
			}else {//两个值相等的情况
				int x = find(nums, 0, nums.length, cp[L]);//找到的第一个
				int y = find(nums, x + 1, nums.length, cp[R]);
				return new int[] {x, y};
			}
		}//这就是没找到
		return new int[] {-1, -1};
	}
	public int find(int[] nums, int begin, int end, int target) {//查找数对应下标
		for(int i = begin; i < end; i++) {
			if(nums[i] == target) {
				return i;
			}
		}
		return -1;
	}
	
//	public int[] twoSum(int[] nums, int target) {
//  int[] ind = new int[nums.length];
//  int[] ans = new int[2];
//  
//  for(int i = 0; i < ind.length; i++) {
//  	ind[i] = i;
//  }
//  //如何对一个数组进行排序 同时又不丢失排序前下标对应的位置
  Arrays.sort(nums, new Comparator<>() {
  	@Override
  	public int compare(int ind[o1], int ind[o2]) {
  		return nums[ind[o1]] - nums[ind[o2]];
  	}
  });
  sort(ind.begin(), ind.end(), [&](int i, int j){
  	return nums[i] < nums[j];
  });
//  for(int i = 0; i < ind.length; i++) {
//  	int j = binarySearch(nums, ind, i + 1, target - nums[ind[i]]);
//  	if(j == -1) continue;
//  	ans[0] = ind[i];
//  	ans[1] = ind[j];
//  	return ans;
//  }
//  
//}
// //不知道为什么会角标越界
//public int binarySearch(int[] nums, int ind[], int i, int target) {
//	int L = i, R = nums.length, mid;
//	while(L <= R) {
//		mid = (L + R) / 2;
//		if(nums[ind[mid]] == target) return mid;
//		else if(nums[ind[mid]] < target) {
//			L = mid + 1;
//		}else {
//			R = mid - 1;
//		}
//	}
//	return -1;
//}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

在D天内送达包裹的能力

/**
 * 在D天内送达包裹的能力
 * @Description:传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
 * 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）
 * 的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。返回能在 days 
 * 天内将传送带上的所有包裹送达的船的最低运载能力。 
 * @author: William
 * @date: 2022-08-18
 */
public class Num1011 {
	//二分查找的初始左右边界应当如何计算呢？对于左边界而言，由于我们不能「拆分」一个包裹，
	//因此船的运载能力不能小于所有包裹中最重的那个的重量，即左边界为数组weights 中元素的最大值。
	//对于右边界而言，船的运载能力也不会大于所有包裹的重量之和，即右边界为数组 weights 中元素的和
	public int shipWithinDays(int[] weights, int days) {
		//确定二分查找左右边界
//		while(L < R) {
//			int mid = (L + R) / 2;
//			//need 为需要运送的天数     cur为当前这一天已经运送的包裹重量之和
//			int need = 1, cur = 0;
//			for(int weight : weights) {
//				if(cur + weight > mid) {
//					++need;
//					cur = 0;
//				}
//				cur += weight;
//			}
//			if(need <= days) {
//				R = mid;
//			}else {
//				L = mid + 1;
//			}
//		}
//		return L;
		int L = Arrays.stream(weights).max().getAsInt();
		int R = Arrays.stream(weights).sum();
		while(L < R) {
			int mid =  (L + R) >> 1;
			//注意 R = mid 
			if(check(weights,mid) <= days) R = mid;//干得比原计划快 可以偷点懒 R收一点
			else L = mid + 1;
		}
		return L;
    }
	
	public int check(int[] nums, int k) {
		int cnt = 1, sum = 0;//天数 和 总和
		for(int num : nums) {
			if(sum + num > k) {//当前重量+可载的重量 > k 说明当前载货的重量已经不行了
				cnt += 1;//包裹需要延后一天进行
				sum = num; //和变成当前包裹的重量
			}else {//可以就一直继续加重量 直到承受不了
				sum += num;
			}
		}
		return cnt;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

将x减到0的最小操作数

/**
 * 将x减到0的最小操作数
 * @Description: 给你一个整数数组nums和一个整数 x 。每一次操作时，
 * 你应当移除数组nums最左边或最右边的元素，然后从 x 中减去该元素的值。
 * 请注意，需要 修改 数组以供接下来的操作使用。
 * 如果可以将x恰好减到 0 ，返回最小操作数否则，返回-1 。
 * @author: William
 * @date: 2022-06-18
 */
public class Num1658 {
	public int minOperations(int[] nums, int x) {
		//分别求出前缀和 与 后缀和  就是两个数组的TwoSum问题
		//使用二分会更快
		int[] sumL = new int[nums.length + 1], sumR = new int[nums.length + 1];
		sumL[0] = sumR[0] = 0;
		for(int i = 0; i < nums.length; i++) {
			sumL[i + 1] = sumL[i] + nums[i];
		}//前缀和
		for(int i = nums.length - 1; i >= 0; i--) {
			sumR[nums.length - i] = sumR[nums.length - i - 1] + nums[i];
		}//后缀和
		int ans = -1;
		
		for(int i = 0; i < sumL.length; i++) {
			int j = binarySearch(sumR, x - sumL[i]);
			if(j == -1) continue;//未找到答案
			if(i + j > nums.length) continue;//左右两边加起来走完了 左右错开
			//否则继续更新ans的值  当前次数更优直接用当前次数
			if(ans == -1 || ans > i + j) {
				ans = i + j;
			}
		}
		return ans;
    }
	
	public int binarySearch(int[] nums, int target) {
		int L = 0, R = nums.length - 1, mid;
		while(L <= R) {
			mid = (L + R) / 2;
			if(nums[mid] == target) {
				return mid;
			}else if(nums[mid] < target) {
				L = mid + 1;
			}else {
				R = mid - 1;
			}
		}
		return -1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

最长递增序列

/**
 * 最长递增序列
 * @Description: 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
 * 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
 * @author: William
 * @date: 2022-06-19
 */
public class Num300 {
	public int lengthOfLIS(int[] nums) {
		if(nums.length == 0) return 0;
		//d[i]: 表示长度为i的最长上升子序列，末尾元素的最小值是多少
		int[] d = new int[nums.length + 1];
		int len = 1;
		d[1] = nums[0];
		for(int i = 0; i < nums.length; i++) {
			if(nums[i] > d[len]) {//表示nums[i]可以添加到d数组最后一个
				len++;
				d[len] = nums[i];//这两行给是动态规划里面的状态转移方程
			}else {//不能塞到最后
				//在len个元素里面，找到一个大于等于nums[i]的元素
				int L = 1, R = len, mid;//状态定义 这个很关键
				while(L <= R) {
					mid = (L + R) / 2;
					if(d[mid] >= nums[i]) {
						R = mid - 1;
					}else {
						L = mid + 1;
					}
				}//R是最后一个小于target的值
				d[R + 1] = nums[i];
			}
		}
		return len;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

在排序数组中查找元素的第一个和最后一个位置

/**
 * 在排序数组中查找元素的第一个和最后一个位置
 * @Description: 
 * @author: William
 * @date: 2022-06-17
 */
public class Num34 {
	public int[] searchRange(int[] nums, int target) {
		int[] ans = new int[2];
		ans[0] = binarySearch(nums, target);
		if(ans[0] == nums.length || nums[ans[0]] != target) {
			ans[0] = ans[1] = -1;//此时没有
			return ans;
		}
		ans[1] = binarySearch(nums, target + 1) - 1;
		return ans;
    }
	
	public int binarySearch(int[] nums, int target) {
		int L = 0, R = nums.length - 1, mid;
		while(L <= R) {
			mid = (L + R) / 2;
			if(nums[mid] >= target) {//找到第一个出现的位置
				R = mid - 1;
			}else {
				L = mid + 1;
			}
		}//最后R肯定不指向target
		return L;//L此时是第一个出现的位置
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

搜索插入位置

/**
 * 搜索插入位置
 * @Description: 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
 * 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 请必须使用时间复杂度为 O(log n) 的算法
 * @author: William
 * @date: 2022-06-17
 */
public class Num35 {
	public int searchInsert(int[] nums, int target) {
        return binarySearch(nums, target);
    }
	//当元素不存在 L指向第一个大于target的值 R指向最后一个小于target的值
	public int binarySearch(int[] nums, int target) {
		int L = 0, R = nums.length - 1, mid;
		while(L <= R) {
			mid = (L + R) / 2;
			if(nums[mid] == target) return mid;
			else if(nums[mid] > target) {//目标在中间的左边
				R = mid - 1;//缩小右边的范围
			} else {
				L = mid + 1;
			}
		}
		return L;//假设000 333 插入一个2 此时2下标应该是右边第一个3那个 对应L下标
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

供暖器

/**
 * 供暖器
 * @Description: 设计一个有固定加热半径的供暖器向所有房屋供暖。
 * 在加热器的加热半径范围内的每个房屋都可以获得供暖。
 * 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，
 * 请你找出并返回可以覆盖所有房屋的最小加热半径。
 * 说明：所有供暖器都遵循你的半径标准，加热的半径也一样
 * @author: William
 * @date: 2022-06-19
 */
public class Num475 {
	public int findRadius(int[] houses, int[] heaters) {
		Arrays.sort(houses);//因为题目没说是有序的
		Arrays.sort(heaters);
		int ans = 0;
		for(int i = 0; i < houses.length; i++) {
			//先找到右边离它最近的供暖器 
			int R = binarySearch(heaters, houses[i]);
			//R==heaters.length就说明没找到，后面没有供暖器   
			//得到第一个离它最近的供暖器的距离
			int dis1 = (R == heaters.length ? Integer.MAX_VALUE : 
				Math.abs(houses[i] - heaters[R]));
			//R==0 表示在最左边 左边没有供暖器了  
			//heaters[R - 1] 离这个房子最近的并且在最左边的供暖器 
			int dis2 = (R == 0 ? Integer.MAX_VALUE : 
				Math.abs(houses[i] - heaters[R - 1]));
			ans = Math.max(ans, Math.min(dis1, dis2));
		}
		return ans;
    }
    
    public int binarySearch(int[] nums, int target) {
    	int L = 0, R = nums.length - 1, mid;
    	while(L <= R) {
    		mid = (L + R) / 2;
    		if(nums[mid] >= target) {
    			R = mid - 1;
    		}else {
    			L = mid + 1;
    		}
    	}
    	return L;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

x的平方根

/**
 * x的平方根
 * @Description: 由于返回类型是整数，结果只保留整数部分 ，小数部分将被 舍去
 * @author: William
 * @date: 2022-06-17
 */
public class Num69 {
	//例如 4和x/4比较大小
	public int mySqrt(int x) {
		if(x == 0 || x == 1) return x;
		int L = 0, R = x, mid;
		while(L <= R) {
			mid = L + (R - L) / 2;//防止越界
			if(mid < (x / mid)) L = mid + 1;
			else if(mid > (x / mid)) R = mid - 1;
			else return mid;
		}
		return R;//因为是向下取整
    }
	
	public int mySqrt1(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

搜索旋转排序数组Ⅱ

/**
 * 搜索旋转排序数组Ⅱ
 * @Description: 
 * @author: William
 * @date: 2022-06-18
 */
public class Num81 {
	//将原来一个非降序数组 旋转之后分成两段 
	//后面那段的最大值x <= 前面那段的最小值y
	//进行一次判断 target < x 在旋转后后面那段 
	//target > y 则在旋转后前面那段 
	public boolean search(int[] nums, int target) {
		//预处理 特判
		if(nums.length == 0) return false;
		if(target == nums[0]) return true;
		int L = 0, R = nums.length - 1;
		while(L < R && nums[L] == nums[0]) L++;
		while(L < R && nums[R] == nums[0]) R--;//当左右两边数组元素分别相同的话
		int head = L, tail = R, mid;//因为每次比较都需要知道最前面和最后面的值
		while(L <= R) {
			mid = (L + R) / 2;
			if(nums[mid] == target) return true;
			else if(nums[mid] <= nums[tail]) {//mid在旋转之后的前面
				if(target > nums[mid] && target <= nums[tail]) {
					L = mid + 1;
				}else {
					R = mid - 1;//直接不要后面那段了
				}
			}else {
				if(target < nums[mid] && target >= nums[head]) {
					R = mid - 1;
				}else {
					L = mid + 1;
				}
			}
		}
		return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

寻找两个正序数组的中位数(hard)

/**
 * 寻找两个正序数组的中位数(hard)
 * @Description: 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2
 * 请你找出并返回这两个正序数组的 中位数 算法的时间复杂度应该为 O(log (m+n))
 * 输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4]
 * 中位数 (2 + 3) / 2 = 2.5
 * @author: William
 * @date: 2022-08-18
 */
public class Num4 {
	//转化为求两个数组中第k小的数 相当于比较两个数组中(k/2) - 1坐标数值的关系
	//假设a的那个小 那个数比((k/2)-1 + (k/2)-1)=k-2个数大 也就是它最多排名k-1 
	//该元素一定是前k个元素而且一定不是第k个元素
	//谁小的那部分可以舍弃掉了
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int n = nums1.length + nums2.length;
		//注意n+1为的是找的 是排名第几的元素
		double a = find(nums1, nums2, 0, 0, (n+1) / 2);
		if(n % 2 != 0) return a;
		//不然找的就是第二位数 指针偏右
		double b = find(nums1, nums2, 0, 0, (n+1) / 2 + 1);
		return (a + b) / 2;
    }
	//k:目标值 第k个元素
	public double find(int[] nums1, int[] nums2, int k1, int k2, int k) {
		if(k1 == nums1.length) return nums2[k2+k-1];//说明第一个为空了 直接返回第二个数组剩余部分排名第k的元素
		if(k2 == nums2.length) return nums1[k1+k-1];//同理
		//说明要找的是两者中小的那个数
		if(k == 1) return nums1[k1] < nums2[k2] ? nums1[k1] : nums2[k2];
		//处理二分的过程 第一二个数组中分别取a和b个元素
		int a = Math.min(k / 2, nums1.length - k1);//判断是否越界
		int b = Math.min(k - a, nums2.length - k2);//注意也要选最小值
		a = k - b;//至此分别选择ab个元素
		if(nums1[k1+a-1] < nums2[k2+b-1]) {
			return find(nums1, nums2, k1+a, k2, k-a);//舍掉nums1的左半部分
		} else {
			return find(nums1, nums2, k1, k2+b, k-b);//舍掉nums2的左半部分
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40