木易

# Road Map

升级路线：

  • 模板题：35
  • 简单二分应用：34 -> 69 -> 278
  • 搜索旋转数组：33 -> 81 -> 153
  • 二分搜索优化：300 -> 354
  • 求最大值最小: 410

# 应用场景

  • 二分都是跟单调性有关，有单调性的题目一般都可以二分。
  • 题目存在两段性的性质。一部分满足，一部分不满足。

# 算法思想

将区间分为左右两边（分治），判断中点，确定答案在哪一边，每次缩小一半，直到得到最终答案。

  • 需要注意边界问题

# 模板

二分模板一共有两个，分别适用于不同情况。

算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l == r时，我们就找到了目标值。

# 模板 1(区间[l, mid]和[mid+1, r])

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，mid=l+r>>1，其更新操作是r = mid或者l = mid + 1;

C++ 代码模板：

int binary_search(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
1
2
3
4
5
6
7
8

此模板返回的结果是右区间的最左边元素

# 模板 2(区间[l, mid-1]和[mid, r])

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，mid=l+r+1>>1，其更新操作是r = mid - 1或者l = mid;

因为r=mid-1，为了防止死循环，计算mid时需要加 1。

C++ 代码模板：

int binary_search(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
1
2
3
4
5
6
7
8

此模板返回的结果是左区间的最右边元素

# 七天学会二分

# 第一天（概念题）

初识二分算法，学习两种二分查找的算法模板

# 852. 山脉数组的峰顶索引 (opens new window)

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int l = 0, r = arr.length-1;
        while(l<r){
            int mid = l+r>>1;
            if (arr[mid] > arr[mid+1]) r = mid;
            else l = mid +1;
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11

选做：

# 第二天（模板强化练习）

通过一道题练习两种模板的使用

# 第三天（峰值元素探险）

# 第四天（有趣的旋转排序数组）

# 153. 寻找旋转排序数组中的最小值 (opens new window)

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

# 154. 寻找旋转排序数组中的最小值 II (opens new window)

把最后等于开头的元素给去掉

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

# 第五天（二维矩阵中的二分）

# 第六天（有序数组中第 Kth 大的数）

无序数组中第 Kth 大的数，也可以使用大小为 K 的小顶堆去求解

如何高效寻找两个有序数组中第 K 大的数？

思考题：

# 第七天（二分，你会了吗？）

单纯的二分算法思路很简单，只需要划分好区间、选对模板、处理好边界即可，一些数据量比较大的且满足一定单调性的题目中，与二分结合使用，会极大提升算法效率（此部分题目需要在掌握其他算法基础之上进行学习）。

← 0x05_排序 →