首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >【二分查找】在排序数组中查找第一个和最后一个位置 / LCR 173. 点名 / 分组

【二分查找】在排序数组中查找第一个和最后一个位置 / LCR 173. 点名 / 分组

作者头像
_小羊_
发布于 2025-04-10 09:02:35
发布于 2025-04-10 09:02:35
5040
举报
文章被收录于专栏:C++C++

并不是只有有序的数组才能用二分查找,只要数组具有二段性,也就是根据某个规则可以分为两段,就可以用二分。

二分查找

代码语言:javascript
复制
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r)
        {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) l = mid + 1;
            else if (nums[mid] > target) r = mid - 1;
            else return mid;
        }
        return -1;
    }
};

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

代码语言:javascript
复制
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0 || target < nums[0] || target > nums[n - 1]) return {-1, -1};
        int begin, l = 0, r = n - 1;
        // 1.找左端点
        while (l < r) // ==会死循环
        {
            int mid = l + (r - l) / 2; // 向下取整
            if (target > nums[mid]) l = mid + 1;
            else r = mid;
        }
        // 2.可能没有目标值
        if (nums[l] != target) return {-1, -1};
        else begin = l;
        l = 0, r = n - 1;
        // 3.找右端点
        while (l < r)
        {
            int mid = l + (r - l + 1) / 2; // 向上取整
            if (target < nums[mid]) r = mid - 1;
            else l = mid;
        }
        return {begin, l};
    }
};

搜索插入位置

为什么最后可以直接 return l,如果没找到目标值,则会由 l > r 出循环。如果是由 r = mid - 1 出的循环,说明此时 mid == l 且所指位置就是要插入的位置;如果是由 l = mid + 1 出的循环,mid所指的元素刚好小于目标值,则出循环后l所指的就是需要插入的位置。

代码语言:javascript
复制
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r)
        {
            int mid = l + (r - l) / 2;
            if (target < nums[mid]) r = mid - 1;
            else if (target > nums[mid]) l = mid + 1;
            else return mid;
        }
        return l;
    }
};

x 的平方根

代码语言:javascript
复制
class Solution {
public:
    int mySqrt(int x) {
        if (x < 1) return 0;
        int l = 1, r = x;
        while (l < r)
        {
            long long mid = l + (r - l + 1) / 2;
            if (mid * mid <= x) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

山脉数组的峰顶索引

不是只有有序数组才能用二分算法,只要数组存在二段性,也就是可以按一定的规则分为两部分,都可以抽象的用二分算法解决问题。 本题就是把数组分为升序和降序两部分。

代码语言:javascript
复制
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int l = 1, r = arr.size() - 2;
        while (l < r)
        {
            int mid = l + (r - l + 1) / 2;
            if (arr[mid] > arr[mid - 1]) l = mid; // 升序 
            else r = mid - 1;
        }
        return l;
    }
};

寻找旋转排序数组中的最小值

代码语言:javascript
复制
class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums.back()) l = mid + 1;
            else r = mid;
        }
        return nums[l];
    }
};

LCR 173. 点名

排序数组中的搜索问题,首先想到的就是二分解法。

代码语言:javascript
复制
class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int l = 0, r = records.size() - 1;
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (records[mid] > mid) r = mid;
            else l = mid + 1; 
        }
        return l == records[l] ? l + 1 : l; // 有可能缺席的是最后一位同学
    }
};

分组

要分到恰好符合题意不太容易,可以换一种思路,枚举符合题目要求的情况下每组最可能多的人数,再用二分优化。

代码语言:javascript
复制
#include <iostream>
#include <unordered_map>
using namespace std;

int n, m;
int a[100001];
unordered_map<int, int> hashmap;

bool check(int x)
{
    int g = 0;
    for (auto [a, b] : hashmap)
    {
        g += b / x + (b % x == 0 ? 0 : 1);
    }
    if (g <= m) return true;
    else return false;
}

int main()
{
    cin >> n >> m;
    int maxcount = 0;
    for (int i = 0; i < n; i++)
    {
        int x; cin >> x;
        maxcount = max(maxcount, ++hashmap[x]);
    }
    if (hashmap.size() > m) cout << -1 << endl;
    else 
    {
        int l = 0, r = maxcount;
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        cout << l << endl;
    }
    return 0;
}

本篇文章的分享就到这里了,如果您觉得在本文有所收获,还请留下您的三连支持哦~

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-04-09,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • 二分查找
  • 在排序数组中查找元素的第一个和最后一个位置
  • 搜索插入位置
  • x 的平方根
  • 山脉数组的峰顶索引
  • 寻找旋转排序数组中的最小值
  • LCR 173. 点名
  • 分组
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档