数据结构与算法-二分查找

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 1.4k | 阅读时间 ≈ 6

前段时间做了几道二分查找的题目，总是不知道对于不同的情况，判定条件要怎么设置。所以就查查资料总结一下。

二分查找思路

这里主要是基于https://labuladong.gitbook.io/algo/mu-lu-ye/er-fen-cha-zhao-xiang-jie的知识再总结。

二分查找是对于一个排序好的数组，找到符合条件的数字位置，比如某一个特定的数，或者找一个数开始和结束的位置。它的模版如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
int binarySearch(vector<int> nums, int target){
    int left = 0, right = ...;
    while(...){
        mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
}

需要注意的就是省略号的位置，需要真的不同情况进行修改。

找到特定的数

首先最简单的情况，就是在有序数组中找到特定的数#704：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(vector<int> nums, int target){
    int left = 0, right = nums.size()-1;
    while(left <= right){
        mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
}

这里的条件都笔记符合直觉，我们在[0,nums.size()]中的区间搜索目标数，如果中间的数就是目标数的时候那么就返回索引；如果中间数小于目标数，那么目标数就会在[mid+1,right]这个范围内；如果中间数大于目标数，那么它会在[left,mid-1]这个范围内。最后，因为搜索区间两边都是[]，所以当left>right的时候就代表全部搜索完了，那么while里的条件就是left <= right。

搜索区间主要是由right初始化的值所决定的，当right=nums.size()-1，那么搜索区间是一个闭合区间，因为nums.size()-1是数组的一个有效的索引。如果right=nums.size()的话，搜索区间就变成半闭半开的了[0,nums.size())。

找到特定数的左边界

搜索区间还是[0,nums.size()]，找到特定数多左边界，我们就需要修改if后面的条件了。首先是等于，等于的时候我们希望继续再往左边搜索，所以要从直接返回mid改成right=mid-1；然后是小于，小于的时候继续往右搜索，left=mid+1；大于的时候和等于一样，继续往左right=mid-1。这里需要注意的是最后返回值的处理，因为有可能target比数组中全部数都要大，需要处理一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(vector<int> nums, int target){
    int left = 0, right = nums.size()-1;
    while(left <= right){
        mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    if (left >= nums.size() || nums[left] != target)
        return -1;
    return left;
}

找到特定数的右边界

有了左边界，右边界就不难了。只需要改一下等于时的条件和越界的条件就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(vector<int> nums, int target){
    int left = 0, right = nums.size()-1;
    while(left <= right){
        mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

二分搜索应用

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

leetcode第34题，找到左右边界。用两个函数实现：

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 binarySearchL(vector<int>& nums, int target){
        int left = 0, right = nums.size()-1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                right = mid - 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        if (left >= nums.size() || nums[left] != target)
            return -1;
        return left;
    }

    int binarySearchR(vector<int>& nums, int target){
        int left = 0, right = nums.size() - 1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                left = mid + 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        if (right < 0 || nums[right] != target)
            return -1;
        return right;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = binarySearchL(nums,target);
        int r = binarySearchR(nums,target);
        return {l,r};
    }
};

74.搜索二维矩阵

在二维矩阵中找有没有目标值，可以用两次二分查找。注意在第一次二分查找的时候，在小于的时候要记录下当前行。复杂度为O(log(mn))

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
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size();
        int rl = 0, rr = n-1;
        int row = 0;
        while (rl <= rr){
            int rm = rl + (rr - rl) / 2;
            if (matrix[rm][0] == target)
                return true;
            else if (matrix[rm][0] > target)
                rr = rm - 1;
            else if (matrix[rm][0] < target){
                row = rm;
                rl = rm + 1;
            }
        }
        int cl = 0, cr = m-1;
        while (cl <= cr){
            int cm = cl + (cr - cl) / 2;
            if (matrix[row][cm] == target)
                return true;
            else if (matrix[row][cm] > target)
                cr = cm - 1;
            else if (matrix[row][cm] < target)
                cl = cm + 1;
        }
        return false;
    }
};

也可以将矩阵“展开”，用一次二分查找，复杂度为O(log(mn))。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = m * n - 1;
        while (l <= r){
            int mid = l + (r - l) / 2;
            int i = mid / m, j = mid % m;
            if (matrix[i][j] == target)
                return true;
            if (matrix[i][j] < target)
                l = mid + 1;
            if (matrix[i][j] > target)
                r = mid - 1;
        }
        return false;
    }
};

参考资料

https://labuladong.gitbook.io/algo/mu-lu-ye/er-fen-cha-zhao-xiang-jie