1. 例题

LC74. 搜索二维矩阵：https://leetcode.cn/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-100-liked

2. 二分法模版

二分法，记住三个模版。模版一是最常用的，不用做后续处理。模版二、三可能要做后续处理。

条件记忆秘诀：看 l 是否 mid + 1，如果 +1 了，mid 在除 2 时就不要 +1。

注意：之所以是否 +1，与死循环有关，本文不做推导。

2.1 模版一

while(l <= r)

mid = (r + l) / 2 = (r - l) / 2 + l

l = mid + 1

r = mid - 1

2.2 模版二

while(l < r)

mid = (r + l) / 2 = (r - l) / 2 + l

l = mid + 1

r = mid

2.3 模版三

while(l < r)

mid = (r + l + 1) / 2 = (r - l + 1) / 2 + l

l = mid

r = mid - 1

3. 解题

3.1 两次二分法

以 LC74. 搜索二维矩阵 为例：

第一次二分查找，套用的是模版三。尝试套模版二行不通。

1
2
3
4
5
6
7
8
9
10
// 进行第一次二分查找
while(top < bottom) {
    mid = (bottom - top + 1) / 2 + top;
    if(matrix[mid][0] <= target) {
        top = mid;
    } else {
        bottom = mid - 1;
    }
}
selectedRow = top; // 找到所在行做后续处理

第二次二分查找，套三个模版均可以，注意后面两个模版要做后续处理。

套模版二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
while(l < r) {
    mid = (r - l) / 2 + l;
    if(matrix[selectedRow][mid] == target){
        return true;
    } else if(matrix[selectedRow][mid] < target) {
        l = mid + 1;
    } else if(matrix[selectedRow][mid] > target) {
        r = mid;
    }
}
// 如果用的另外两个模版，要在最后判定一次l或者r
if(matrix[selectedRow][l] == target){
    return true;
}

套模版三：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
while(l < r) {
    mid = (r - l + 1) / 2 + l;
    if(matrix[selectedRow][mid] == target){
        return true;
    } else if(matrix[selectedRow][mid] < target) {
        l = mid;
    } else if(matrix[selectedRow][mid] > target) {
        r = mid - 1;
    }
}
// 如果用的另外两个模版，要在最后判定一次l或者r
if(matrix[selectedRow][l] == target){
    return true;
}

套模版一（完整代码），不用后续处理：

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
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int height = matrix.length, width = matrix[0].length;
        int top = 0, bottom = height - 1;
        int selectedRow = -1;
        int mid = -1;
        // 进行第一次二分查找
        while(top < bottom) {
            mid = (bottom - top + 1) / 2 + top;
            if(matrix[mid][0] <= target) {
                top = mid;
            } else {
                bottom = mid - 1;
            }
        }
        selectedRow = top;
        // 进行第二次二分查找
        int l = 0, r = width - 1;
        while(l <= r) {
            mid = (r - l) / 2 + l;
            if(matrix[selectedRow][mid] == target){
                return true;
            } else if(matrix[selectedRow][mid] < target) {
                l = mid + 1;
            } else if(matrix[selectedRow][mid] > target) {
                r = mid - 1;
            }
        }
        return false;
    }
}

3.2 一次二分法

套用模版二，一样要做后续处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 一次二分查找
        int height = matrix.length, width = matrix[0].length;
        int l = 0, r = height * width - 1;
        int mid = 0;
        while (l < r) {
            mid = (r - l) / 2 + l;
            if (matrix[mid / width][mid % width] == target) {
                return true;
            } else if (matrix[mid / width][mid % width] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        // 后续判断
        mid = (r - l) / 2 + l;
        if (matrix[mid / width][mid % width] == target) {
            return true;
        }
        return false;
    }
}