发表更新数据结构与算法 / 数组与字符串14 分钟读完 (大约2168个字)

二分法

二分法的框架好写，但正确的二分法难写。

私以为：二分法的精髓在于，每次迭代时，保留答案存在的区间或者丢弃答案不存在的区间，从而缩小查找范围。

需要注意的是：保留答案存在的区间时，需要避免无限循环；二分区间状态转移的一致性。

题单：https://leetcode.cn/studyplan/binary-search/

有序不重复数组

简单二分

单调递增数组找目标元素下标，元素不重复，目标元素不在其中则返回-1。

https://leetcode.cn/problems/binary-search/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int search(int[] nums, int target) {
       int l=0, r=nums.length -1;
       while(l <= r){
            int mid = (l+r)/2;
            if(nums[mid] == target) return mid;
            if(nums[mid] < target)
                l = mid + 1;
            else
                r = mid - 1;
       } 
       return -1;
    }
}

看起来很简单，对吧。但是我们思考以下几个问题：

  • l，r的初始值
  • while循环中 l<r 还是 l<=r
  • mid的向下取整问题，当前写法(l+r)/2存在向下取整问题， $left \le mid <right $

前两个问题我们可以得出结论：

  • l、r的初始值代表着区间表示法
  • while循环中，代表着当前仍在合法区间内

举例子：

1
2
3
4
5
int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
  
int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <

换成左闭右开的写法后，right就不再是mid-1了，因为左闭右开区间自然不包括右边的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) {
                left = mid + 1;
            } else { 
                right = mid; // target 在左区间，在[left, middle)中
            }
        }
        return -1;
    }
}

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

比如数组【1】，元素0返回下标0，元素1返回下标0，元素2返回下标1。

https://leetcode.cn/problems/search-insert-position/

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
class Solution {
    public int searchInsert(int[] nums, int target) {
        int l=0, r=nums.length-1;
        while(l<=r){
            int mid = (r+l) / 2;
            if(nums[mid]>=target)
                r=mid-1;
            else 
                l=mid+1;
        }
        return l; // 最后l==r-1
    }
}

class Solution {
    public int searchInsert(int[] nums, int target) {
       int l = 0, r = nums.length;
       while(l < r){
            int mid = (l+r) / 2;
            if(nums[mid]>=target)
                r = mid;
            else
                l = mid+1;
       } 
       return l; // 最后l==r
    }
}

将每一次缩小区间的过程看成一次状态转移：从一个大区间到一个小区间，其中状态转移的一致性就是指永远保留答案在我的窗口区间内（或者每次舍弃答案不在的区间）。

这里两种写法的区别并不大，需要注意的是返回值，第一种写法返回l或者r+1，第二种写法返回l或者r都行。

旋转排序数组中的最小值

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findMin(int[] nums) {
        int l=0, r=nums.length-1;
        if(nums[l]<=nums[r]) return nums[l];
        while(l<r && nums[l]>nums[r]){
            int mid = (l+r)>>1;
            if(nums[mid]>=nums[l]){
                l = mid+1; // mid一定落在左区间
            }else{
                r = mid;  // mid一定落在右区间
            }
        }
        return nums[l]; // l==r 构成单元素区间，直接返回
    }
}

旋转排序数组，其实是分成了两个有序段，左半段和右半段，左半段的值肯定是大于右半段的值。

这题的难点在于：

  • 左右两段的情况同时存在
  • 应用二分法的过程中，可能从两个段跨越到一个段，导致语义错误

那么我就应用状态机的思想，维持我left和right的区间始终为两个段的情况（nums[l]>nums[r])，如果跨越到右半段，直接返回右半段的最左边的值。

贴上mid和right比较的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findMin(int[] nums) {
        int l=0, r=nums.length-1;
        while(l<r){
            int mid = (l+r)>>1;
            if(nums[mid] < nums[r]){ // mid必定落在右区间，安全收缩
                r = mid;
            }else{  // mid必定落在左区间，安全收缩
                l = mid+1;
            }
        }
        return nums[l];
    }
}

搜索旋转排序数组

给你一个target，在旋转排序数组中找它的下标，不存在返回-1。

https://leetcode.cn/problems/search-in-rotated-sorted-array/

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
class Solution {
    public int search(int[] nums, int target) {
        if(nums==null||nums.length==0) return -1;
        int l=0, r=nums.length-1;
        while(l<=r){
            int mid = (l+r)>>1;
            if(nums[mid] == target) return mid;
            // 先判断mid在左半段还是右半段
            if(nums[l] <= nums[mid]){ 
                // 再判断target在段中的左右
                if(nums[l] <= target && target < nums[mid]){
                    r = mid-1;
                }else{
                    l = mid+1;
                }
            }else{
                if(nums[mid] < target && target <= nums[r]){
                    l = mid+1;
                }else{
                    r = mid-1;
                }
            }
        }
        return -1;
    }
}

这道题的难点还是在于：存在两段单调递增的区间，中点值与target值的比较无法引导区间的缩小。

观察到：mid一定落在两个单调递增的区间中的一个，如果mid落在左区间，那么left与mid构成单调区间；如果mid落在右区间，mid与right构成单调区间。如果target落在这段单调区间，那么就能二分；如果target没有落在这段单调区间，正好，这段单调区间可以舍弃。

怎么判断mid落在哪段单调区间呢？

观察到：

  • 如果nums[l] <.nums[r] 则只有一个单调区间，直接二分
  • 如果nums[l]>nums[r]
    • mid落在左区间，则$nums[mid]>=nums[l], nums[mid]>nums[r]$
    • mid落在右区间，则$nums[mid]<nums[l], nums[mid]<=nums[r]$
    • 上述取到等于号时，是因为区间和 mid的计算方式，可能使得mid==l或者r

有序重复数组

排序数组寻找元素第一个和最后一个位置

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

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
class Solution {
public:
    // find first value that satisfis value >= target
    int lowerBound(vector<int>& nums, int target){
        int l=0,r=nums.size();
        int mid;
        while(l < r){
            mid = (l+r)/2;
            if(nums[mid] >= target){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }

    // find first value that satisfis value > target
    int upperBound(vector<int>& nums, int target){
        int l=0,r=nums.size();
        int mid;
        while(l < r){
            mid = (l+r)/2;
            if(nums[mid] > target){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
  
    vector<int> searchRange(vector<int>& nums, int target) {
        int first = lowerBound(nums, target); 
        int second = upperBound(nums, target);
        if (first==nums.size() || nums[first]!=target){
            return {-1, -1};
        }
        // first guarantee target exist in vector
        return {first, second-1};
    }
};

Lower_bound 的语义：有序重复数组寻找目标元素第一次出现的位置，如果不存在，返回应该插入的位置。

Upper_bound 的语义：有序重复数组寻找大于目标元素的数字第一次出现的位置，如果不存在，返回应该插入的位置。

换位思考：先求序列中第一个大于x的元素的位置，然后减1就是x最后出现的位置。

泛化

通过思考可以发现，lower和upper函数都在解决这样一个问题：在一个有序序列中第一个满足某条件的元素的位置。

lower-bound就是，从左到右，找第一个满足值“大于等于”target的元素。

upper-bound就是，从左到右，找第一个满足值”大于“target的元素。

于是就有了这样一个模版：

1
2
3
4
5
6
7
8
9
10
11
//从左到右，找第一个满足条件的元素位置
int solve(int left, int right){
	while(left < right){
		int mid = (left+right)/2;
		if(条件成立) //我们要找条件成立的第一个位置！
			right = mid; //所以继续往左区间找
		else
		 	left = mid+1;
	}
	return left;
}

这个函数解决在某序列中，从左到右，第一个满足条件的元素下标。

比如求最后一个x<4的元素下标，数组为[1,2,2,2,5]，答案为3。

先求第一个满足x>=4的下标，为4，然后减去1，得到答案3。

搜索旋转排序数组2

给你一个target，在旋转排序数组（这个数组可能含有重复元素）中找它的下标，不存在返回-1。

https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/

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
class Solution {
    public boolean search(int[] nums, int target) {
        if(nums==null||nums.length==0) return false;
        int l=0, r=nums.length-1;
        while(l<=r){
            int mid = (l+r)>>1;
            if(nums[mid] == target) return true;
            // ---相等的情况,可能l==mid,也可能l!=mid---
            if(nums[l] == nums[mid]) {l++;continue;}
          	// -------------------------------------
            if(nums[l] < nums[mid]){ 
                if(nums[l]<= target && target < nums[mid]){
                    r = mid-1;
                }else{
                    l = mid+1;
                }
            }else{
                if(nums[mid]<target && target<=nums[r]){
                    l = mid+1;
                }else{
                    r = mid-1;
                }
            }
        }
        return false;
    }
}

这里比上题就多出了一行代码:

1
if(nums[l] == nums[mid]) {l++;continue;}

题目

keke吃香蕉

https://leetcode.cn/problems/koko-eating-bananas/description/

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
class Solution {
    public int solve(int[] piles, int speed){
        // 以speed的速度解决这堆香蕉需要多久
        int time = 0;
        for(int banana: piles){
            //上取整的实现
            time += (banana+speed-1)/speed;
        } 
        return time;
    }
    public int minEatingSpeed(int[] piles, int h) {
        // 最小速度1，最大速度max（piles）
        // 最大速度解释：piles.length <= h , 最大速度一定可以在length小时吃完
        int l =1, r = -1;
        for(int pile:piles){
            r = Math.max(r, pile);
        }
        while(l < r){
            int mid = (l+r)/2;
            int time = solve(piles, mid);
            if(time<=h){ //速度过快，往小的方面搜索
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return r;
    }
}

最小速度可以为1，但1不保证能在h小时吃完所有香蕉。最大速度怎么求？无限大？只要找到一个能在h小时吃完所有香蕉的速度speed就行。这个speed是个上界，但不是上确界。

小技巧：上取整的实现

  • $\lceil p/s \rceil = \lfloor (p+s-1)/s \rfloor$

  • 利用带余除法判断，余数是否大于0

1
int time = p/s + (p%s>0) ? 1:0;

货物运输

https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/

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
class Solution {
    public int transit(int[] weights, int load){
        int day = 0;
        int cur = 0; // 目前载荷
        for(int weight:weights){
            if(cur+weight <load){
                cur += weight;
            }else if(cur+weight ==load){
                ++day;
                cur = 0;
            }
            else{
                ++day;
                cur = weight;
            }
        }
        if(cur>0) ++day;
        return day;
    }
    public int shipWithinDays(int[] weights, int days) {
        // 最小max(weights)，最大sum（weights）
        int l =0, r=0;
        for(int weight:weights){
            r += weight;
            l = Math.max(l , weight);
        }
        System.out.println(transit(weights, 5));
        while( l < r){
            int mid = l + (r-l)/2;
            int day = transit(weights, mid);
            if(day <= days){ 
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return r;
    }
}

这题与上面一题几乎一样！注意点：

1、左右边界的确定

左边界是weights的最大，因为船至少能装一个货物。最大就是求和，这样能在一天运完。

2、计算当前负载需要天数的函数

用模拟方式进行，负载装满就出发。

总结

在应用二分法，注意左右边界的获取。

根据区间的表示法，选择合适while循环判断条件。

在应用二分法时，每次缩小区间，其实是排除不符合条件的区间过程。

状态转移的一致性就是指永远保留答案在我的窗口区间内（每次舍弃答案不在的区间）。

二分法

https://xyz.desirer233.fun/2023/12/22/数据结构与算法/数组与字符串/二分法/

作者

Desirer

发布于

2023-12-22

更新于

2026-04-21

许可协议

#

分类

×