Skip to main content

二分查找

· 9 min read
therainisme
therainisme
快乐！

预习一下 lower_bound 的用法与写法​

lower_bound 功能：在连续递增的数组中返回一个下标 i，其对应的数为 x。给定目标值 t，x 是第一个满足 t <= x 的数。

例如，下面的序列中，当 t = 2 时，lower_bound 返回的 i 为 2。

1 1 *2* 2 3 4 5 5 6

写法​

灵茶山艾府提供了一版“开区间” lower_bound 的写法，记忆点：

  1. 初始端点都取不到，l = -1, r = n。
  2. while 里 l + 1 < r
  3. 防止溢出，mid = l + (r - l) / 2。
  4. if 和 else 更新 l 和 r 时都不需要加 1 或减 1。
int lower_bound(int t) {
    int l = -1, r = n;
    while(l + 1 < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= t) r = mid;
        else l = mid;
    }
    return l;
}

记不住也可以使用 C++ 的 STL：

lower_bound(nums.begin(), nums.end(), t);

用法​

本质上所有对区间的求解都可以使用 lower_bound 替代：

  1. 求 t <= x，为 lower_bound(t)。
  2. 求 t < x，为 lower_bound(t + 1)，求第一个大于 t 的数。
  3. 求 x < t，为 lower_bound(t) - 1，求第一个大于等于 t 的数，下标再减 1。
  4. 求 x <= t，为 lower_bound(t + 1) - 1，求第一个大于等于 t + 1 的数，下标再减 1。

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

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

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int t) {
        auto lx = lower_bound(nums.begin(), nums.end(), t);
        if (lx == nums.end() || *lx != t) {
            return vector<int>{-1, -1};
        }
        auto rx = lower_bound(nums.begin(), nums.end(), t + 1) - 1;
        return vector<int>{
            static_cast<int>(lx - nums.begin()),
            static_cast<int>(rx - nums.begin())
        };
    }
};
题解

t 元素第一个出现位置，即为第一个满足 t <= x 的数，可用 lower_bound(t) 直接求解。

t 元素最后一个出现位置，即为第一个满足 t + 1 <= x 的数的下标减 1，转变思路，可用 lower_bound(t + 1) - 1 直接求解。

35.搜索插入位置​

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4
class Solution {
public:
    int searchInsert(vector<int>& nums, int t) {
        auto it = lower_bound(nums.begin(), nums.end(), t);
        if (it == nums.end()) {
            return nums.size();
        }
        return static_cast<int>(it - nums.begin());
    }
};
题解

仅需要特别处理一下该元素不存在，且 it 指针位于数组末尾的情况，此时插入的位置应该为数组的末尾。其余情况均为 lower_bound(t) 的解。

2529.正整数和负整数的最大计数​

示例 1：

输入：nums = [-2,-1,-1,1,2,3]
输出：3
解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 2：

输入：nums = [-3,-2,-1,0,0,1,2]
输出：3
解释：共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 3：

输入：nums = [5,20,66,1314]
输出：4
解释：共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。
class Solution {
public:
    int maximumCount(vector<int>& nums) {
        auto lx = lower_bound(nums.begin(), nums.end(), 0);
        auto rx = lower_bound(nums.begin(), nums.end(), 1);
        return max(lx - nums.begin(), nums.end() - rx);
    }
};
题解

对于负整数，需要通过 lower_bound 找到第一个大于等于 0 的数，即 lower_bound(0)。负整数的数量为第一个大于等于 0 的数的下标。

对于正整数，需要找到最后一个大于 0 的数，可以转换成大于等于 1 的数，即 lower_bound(1)。正整数的数量为数组长度减去该数的下标。

得到两个结果取最大值，求得答案。

1146. 快照数组​

class SnapshotArray {
public:
    unordered_map<int, vector<pair<int, int>>> array;
    int snapshot_call = 0;

    SnapshotArray(int length) {
        for (int i = 0; i < length; i++) {
            array[i].push_back({0, 0});
        }
    }
    
    void set(int index, int val) {
        array[index].push_back({snapshot_call, val});
    }
    
    int snap() {
        int rt = snapshot_call;
        snapshot_call += 1;
        return rt;
    }
    
    int get(int index, int snap_id) {
        vector<pair<int, int>>& nums = array[index];
        int l = -1, r = nums.size();
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid].first >= snap_id + 1) r = mid;
            else l = mid;
        }
        return nums[r - 1].second;
    }
};
题解

我们需要记录每一个 index 对应下标的更新记录，使用 pair<int, int>，first 为 snap_id，second 为 value。

在 get 操作传入时，通过传入的 snap_id 对其二分搜索，目标是找到该 snap_id 的最后一个 value。即查找 lower_bound(snap_id + 1) 再下标减 1。

911. 在线选举​

输入：

["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
persons = [0, 1, 1, 0, 0, 1, 0]
times   = [0, 5, 10, 15, 20, 25, 30]
qs = [3], [12], [25], [15], [24], [8]

输出：

[null, 0, 1, 1, 0, 0, 1]

解释：

TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // 返回 0 ，在时刻 3 ，票数分布为 [0] ，编号为 0 的候选人领先。
topVotedCandidate.q(12); // 返回 1 ，在时刻 12 ，票数分布为 [0,1,1] ，编号为 1 的候选人领先。
topVotedCandidate.q(25); // 返回 1 ，在时刻 25 ，票数分布为 [0,1,1,0,0,1] ，编号为 1 的候选人领先。（在平局的情况下，1 是最近获得投票的候选人）。
topVotedCandidate.q(15); // 返回 0
topVotedCandidate.q(24); // 返回 0
topVotedCandidate.q(8); // 返回 1
class TopVotedCandidate {
public:
    vector<int> win_time;
    vector<int> winner;

    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        unordered_map<int, int> votes;
        int win_votes = 0;
        int win_person = 0;
        for (int i = 0; i < times.size(); i ++) {
            votes[persons[i]] += 1;
            if (win_time.empty() || votes[persons[i]] >= win_votes) {
                win_votes = votes[persons[i]];
                win_person = persons[i];

                win_time.push_back(times[i]);
                winner.push_back(persons[i]);
            } else {
                win_time.push_back(times[i]);
                winner.push_back(win_person);
            }
        }
    }
    
    int q(int t) {
        auto it = lower_bound(win_time.begin(), win_time.end(), t + 1) - 1;
        return winner[it - win_time.begin()];
    }
};
题解

预先持久化每一个时间节点上的胜者，查询时通过 t 二分查询，找到最后一个小于等于 t 的时间节点上的胜者。例如：

  1. 当 t = 24 时，应该找到的是 20 而不是 25。
  2. 当 t = 25 时，应该找到的是 25
0 5 10 15 20 25 30

资料​