思想

找到一个性质，使得区间分成两段，一段满足，一段不满足。然后找到断点

左区间的右端点

int l = 0, r = n;
while (l < r) {
    int m = l + r + 1 >> 1;
    if (check(m)) l = m;
    else r = m - 1;
}

右区间的左端点

int l = 0, r = n;
while (l < r) {
    int m = l + r >> 1;
    if (check(m)) r = m;
    else l = m + 1;
}

题目

x 的平方根 https://leetcode-cn.com/problems/sqrtx/

性质：m * m ≤ x，找到一个最大的 m

class Solution {
public:
    int mySqrt(int x) {
        long long l = 0, r = x;
            while (l < r) {
            long long m = (l + r + 1) >> 1;
            if (m * m <= x) l = m;
            else r = m - 1;
        }
        return l;
    }
};

性质：m * m > x，找到一个最小的 m，答案是 m - 1

class Solution {
public:
    int mySqrt(int x) {
        long long l = 0, r = x + 1ll;
            while (l < r) {
            long long m = (l + r) >> 1;
            if (m * m > x) r = m;
            else l = m + 1;
        }
        return l - 1;
    }
};

搜索插入位置 https://leetcode-cn.com/problems/search-insert-position/

性质：m ≥ x，找到一个最小的 m

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if (nums.size() == 0) return 0;
        if (target > nums.back()) return nums.size();
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int m = (l + r) >> 1;
            if (nums[m] >= target) r = m;
            else l = m + 1;
        }
        return r;
    }
};

在排序数组中查找元素的第一个和最后一个位置 https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

性质：找一个区间，区间左端点是 m ≥ x 最小的m，区间右端点是 m > x，最小的 m

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (!nums.size()) return vector<int>{-1, -1};
        vector<int> ans;
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int m = (l + r) >> 1;
            if (nums[m] >= target) r = m;
            else l = m + 1;
        }
        if (nums[l] != target) return vector<int>{-1, -1};
        ans.push_back(l);

        l = 0, r = nums.size() - 1;
        while (l < r) {
            int m = (l + r + 1) >> 1;
            if (nums[m] <= target) l = m;
            else r = m - 1;
        }
        ans.push_back(l);
        return ans;
    }
};

纯STL实现

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto begin = lower_bound(nums.begin(), nums.end(), target);
        auto end = upper_bound(nums.begin(), nums.end(), target);
        int a = begin == nums.end() ? -1 : (*begin == target ? begin - nums.begin() : -1);
        int b = a == -1 ? -1 : (end == nums.end() ? nums.size() - 1 : end - nums.begin() - 1);
        return vector<int>{a, b};
    }
};

搜索二维矩阵 https://leetcode-cn.com/problems/search-a-2d-matrix/

性质，m ≥ x 最小的 m，答案判断下是否等于

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int l = 0, r = matrix.size() * matrix[0].size() - 1;
        int m = matrix.size(), n = matrix[0].size();
        while (l < r) {
            int mid = l + r >> 1;
            if (matrix[mid/n][mid % n] >= target) r = mid;
            else l = mid + 1;
        }
        return matrix[l/n][l%n] == target;
    }
};

纯 STL 实现

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        vector<int> a;
        for (auto vec : matrix)
            for (auto item : vec) a.push_back(item);

        auto it = lower_bound(a.begin(), a.end(), target);
        if (it == a.end() || *it != target) return false;
        return true;
    }
};

寻找旋转排序数组中的最小值 https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

性质：a[m] ≤ a.back() ，找到最小的 m，即右区间的左端点

class Solution {
public:
    int findMin(vector<int>& nums) {
        auto check = [&](int pos) {
            return nums[pos] <= nums.back();
        };
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int m = l + r >> 1;
            if (check(m)) r = m;
            else l = m + 1;
        }
        return nums[l];
    }
};

搜索旋转排序数组 https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

性质：找到最小值，把数组分成两段，然后二分查找
纯STL实现

class Solution {
public:
        // 尝试完全用 STL 里的 lower_bound 和 upper_bound 代替手写二分
        // lower_bound 对应的是 找一个最靠右的 check(x) == true
        // upper_bound 对应的是找一个最靠左的 check(x) == true
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;

        auto div = upper_bound(nums.begin(), nums.end(), nums.back(), [&](int a, int b) { return a >= b; });
        auto it = nums.begin();

        if (target <= nums.back()) it = lower_bound(div, nums.end(), target);
        else it = lower_bound(nums.begin(), div, target);

        if (it == nums.end() || *it != target) return -1;
        return it - nums.begin();
    }
};

寻找峰值 https://leetcode-cn.com/problems/find-peak-element/

性质：
如果当前点不是峰值，如果 a[m] < a[m + 1] 那么右区间一定有答案，否则答案一定在左区间
a[m] ≥ a[m + 1] 最小的 m （这里的最小不是真正意义上的最小，而是指^这一段的最小），即右端点的左区间

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int m = l + r >> 1;
            if (nums[m] < nums[m + 1]) l = m + 1;
            else r = m;
        }
        return l;
    }
};

寻找重复数 https://leetcode-cn.com/problems/find-the-duplicate-number/

性质：m > cnt 最小的 m
这里用到了抽屉原理，n + 1 个数，放进 n 个抽屉，一定会有一个放了一个以上数的抽屉，那么我们枚举这个抽屉数
比如 1 2 3 4 2
l = 1, r = 4
m = 2:
cnt = 3, r = 2
l = 1, r = 2
m = 1:
cnt = 1, l = 2

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r) {
            int m = l + r >> 1;
            int cnt = 0;
            for (auto i : nums) if (i <= m && i >= l) cnt++;
            // 要找一个最小的 m，使得 [l, m] 这 m - l + 1 个坑 < cnt
            if (m - l + 1 < cnt) r = m;
            else l = m + 1;
        }
        return l;
    }
};

H指数 II https://leetcode-cn.com/problems/h-index-ii/

性质：a[n - m - 1 + 1] ≥ m，找到一个最大的 m，即左区间的右端点

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int l = 0, r = citations.size();
        while (l < r) {
            // 找到一个最大的 m，使得 h[r - m] >= m，因为下标从0开始
            int m = l + r + 1 >> 1;
            if (citations[citations.size() - m] >= m) l = m;
            else r = m - 1;
        }
        return l;
    }
};

算法学习笔记

二分专题

思想