【剑指offer|图解|二分查找】点名 + 统计目标成绩的出现次数

🌈个人主页：聆风吟
🔥系列专栏：剑指offer每日一练
🔖少年有梦不应止于心动，更要付诸行动。

---

一. ??点名

? 在线OJ链接,可以转至此处自行练习 ?

1.1 题目

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。

1.2 示例

输入： records = [0,1,2,3,5]
输出： 4

1.3 限制

• 1 <= records.length <= 10000

1.4 解题思路一

二分查找
根据题意，数组可以按照以下规则进行划分为两部分：

• 左子数组：records[i] = i
• 右子数组：records[i] != i

缺失的数字等于 右子数组的首位元素 对应的索引，因此我们可以使用二分查找右子数组首元素。

算法执行过程：

1. 初始化 ：左边界 l = 0 和 右边界 r = records.size() - 1
2. 循环二分：当 l <= r 时循环
   • 计算中心点 mid = (l + r) / 2;
   • 如果 records[mid] = mid 说明要查找的值在区间[mid + 1, r] 之间，因此执行 l = mid + 1;
   • 如果 records[mid] != mid 说明要查找的值在区间[l， mid - 1] 之间，因此执行 r = mid - 1;
3. 返回值：循环跳出时，返回 l 即可。

c++代码

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int sz = records.size();

        int l = 0;
        int r = sz - 1;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(records[mid] == mid) l = mid + 1;
            else r = mid -1;
        }

        return l;
};

1.5 解题思路二

求和做差
有题目可知：
将 0 ~ n - 1 之间所有同学的学号加在一起，然后减去数组中的每个元素，所得结果即是缺课人学号。

c++代码

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        
        int sz = records.size();
        int sum = sz*(sz+1)/2;//使用等差求和公式求全班学号的总和
        
        //将全班人的学号 - 数组中的每一个元素
        for(int i = 0; i < sz; i++)
        {
            sum -= records[i];
        }

        return sum;
    }
};

---

二. ??统计目标成绩的出现次数

? 在线OJ链接,可以转至此处自行练习 ?

1.1 题目

某班级考试成绩按非严格递增顺序记录于整数数组 scores，请返回目标成绩 target 的出现次数。

1.2 示例

输入： scores = [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target = 4
输出： 3

1.3 限制

• 0 <= scores.length <= 105
• -109 <= scores[i] <= 109
• scores 是一个非递减数组
• -109 <= target <= 109

1.4 解题思路

对于已经排好序的数组查找问题，首先我们可以想到是用二分查找。

对于排序数组 scores 中所有数字 target 形成一个窗口，记做窗口的 左 / 右边界 索引分别为 left 和 right，分别对应窗口的左右两边。因此本题求数字 target 出现的次数，就可以转化为：使用二分法分别求出窗口的左边界 left 和 右边界 right，容易得出数字 target 出现的次数 right - left + 1。



1. 查找右边界：

//查找右边界
while(l < r)
{
	int mid = (l + r + 1) >> 1;
    if(scores[mid] <= target) l = mid;
    else r = mid - 1;
}

注意：

1. 在查找完右边界后，需要用 scores[right] 判断一下数组中是否含有 target，若不包含则直接提前返回 0，无需继续查找左边界
2. 记得让指针 l，r 重新回到起点处

2. 查找左边界：

//查找左边界
while(l < r)
{
	int mid = (l + r) >> 1;
	if(scores[mid] >= target) r = mid;
	else l = mid + 1;
}

由于左边界的查找同右边界运行类似，大家可以在下面自己画出图形，调试。

c++代码

class Solution {
public:
    int countTarget(vector<int>& scores, int target) {
        int sz = scores.size();
        int l = 0;
        int r = sz - 1;

        // 搜索右边界
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(scores[mid] <= target) l = mid;
            else r = mid - 1;
        }
        int right = r;

        // 若数组中无 target ，则提前返回
        if(r >= 0 && scores[right] != target) return 0;

        // 搜索左边界
        l = 0, r = sz - 1;//让指针返回到初始状态
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(scores[mid] >= target) r = mid;
            else l = mid + 1;
        }
        int left = l;

        return right - left + 1;
    }
};

---

📝结语

???? 今天的干货分享到这里就结束啦！如果觉得文章还可以的话，希望能给个三连支持一下，聆风吟的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的最大动力！