当前位置: 首页 > article >正文

【打卡D6】二分法

整数二分算法模板 —— 模板题 AcWing 789. 数的范围
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int left_search(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足某种性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int right_search(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if
(check(mid)) l = mid;
        else r = mid - 1;

注意:有+就有-
    }
    return l;
}

二分法(Binary Search)详解

二分法(Binary Search)是一种经典的 分治算法,常用于在 已排序的数组区间 中查找目标值。其核心思想是通过不断将搜索区间对半分,缩小查找范围,从而 高效 地找到目标元素。二分法的时间复杂度是 O(log n),因此在处理大规模数据时非常高效。

基本思想

二分查找的核心思路是:

  1. 将待查找的区间分成两部分,根据中间元素与目标值的比较结果决定下一步搜索的区间。
  2. 继续在新的一半区间内查找,不断缩小查找的范围,直到找到目标元素,或确认目标元素不在数组中。
基本步骤
  1. 初始化区间:设定两个边界,通常是 左边界 l右边界 r,表示当前查找的范围。
  2. 计算中间位置 mid:每次计算中间位置 mid = (l + r) / 2(或者使用 mid = l + (r - l) / 2 来防止溢出)。
  3. 比较中间值与目标值
    • 如果中间值等于目标值,则 找到了目标
    • 如果中间值大于目标值,则目标值可能在中间值的左侧,因此 将右边界 r 移动到 mid - 1
    • 如果中间值小于目标值,则目标值可能在中间值的右侧,因此 将左边界 l 移动到 mid + 1
  4. 停止条件:当 左边界 l 不再小于右边界 r,说明找到了目标,或者目标不在数组中。

例:假设数组 a = {1, 2, 2, 3, 3, 3, 4, 5, 5},并查询 x = 3,左边界右边界的位置

  1. 查找左边界

    • 使用 searchleft(0, 8, 3),通过二分查找,返回第一个 3 出现的位置,结果是 3
  2. 查找右边界

    • 使用 searchright(0, 8, 3),通过二分查找,返回最后一个 3 出现的位置,结果是 5
  3. 输出

#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1e5 + 10; // 定义数组大小的上限
int a[N]; // 数组,用来存储输入的已排序整数

// 左边界
int searchleft(int l, int r, int x) {
    while (l < r) {  // 当左右边界还未收敛时
        int mid = (r + l) >> 1;  // 计算中间位置
        if (a[mid] >= x) r = mid;  // 如果中间值大于等于 x,则右边界收缩
        else l = mid + 1;  // 如果中间值小于 x,则左边界收缩
    }
    return l;  // 返回左边界位置,表示第一个大于等于 x 的位置
}

// 右边界
int searchright(int l, int r, int x) {
    while (l < r) {  // 当左右边界还未收敛时
        int mid = (l + r + 1) >> 1;  // 计算中间位置,偏向右侧
        if (a[mid] <= x) l = mid;  // 如果中间值小于等于 x,则左边界收缩
        else r = mid - 1;  // 如果中间值大于 x,则右边界收缩
    }
    return r;  // 返回右边界位置,表示最后一个小于等于 x 的位置
}

int main() {
    int n, q;  // n 为数组的长度,q 为查询次数
    cin >> n >> q;  // 输入数组长度和查询次数
    for (int i = 0; i < n; i++) cin >> a[i];  // 输入已排序数组

    while (q--) {  // 循环处理每一个查询
        int x;  // 当前查询的目标数字
        cin >> x;  // 输入要查询的数字 x

        // 查找第一个大于等于 x 的位置,使用左边界二分查找
        int l = searchleft(0, n - 1, x);
        
        // 如果 l 指向的不是 x,说明数组中没有 x
        if (a[l] != x) {
            cout << "-1 -1" << endl;  // 输出 -1 -1,表示 x 不在数组中
        } else {
            // 查找最后一个小于等于 x 的位置,使用右边界二分查找
            int r = searchright(0, n - 1, x);
            // 输出左边界和右边界,即 x 的第一次和最后一次出现的位置
            cout << l << " " << r << endl;
        }
    }

    return 0;  // 返回 0,程序正常结束
}


http://www.kler.cn/a/587395.html

相关文章:

  • 计算机网络-TCP/IP协议族
  • Vue:收集表单数据过滤器
  • 深入理解 HTML 中的<div>和元素:构建网页结构与样式的基石
  • phpstudy+phpstorm+xdebug【学习笔记】
  • IDEA集成git,项目的克隆,远程仓库中文件的添加删除
  • AI Agent 时代开幕-Manus AI与OpenAI Agent SDK掀起新风暴
  • STL标准库
  • C++20中的`std::endian`:深入理解大端/小端/本地字节序
  • Ubuntu 20.04使用阿里源并更新glibc到2.35版本
  • X86 RouterOS 7.18 设置笔记八:策略路由及DNS劫持
  • 剑指 Offer II 086. 分割回文子字符串
  • Redis 的应用场景
  • MyBatis SqlSessionFactory 是如何创建的?
  • 什么是 slot-scope?怎么理解。
  • 组合Ⅲ 力扣216
  • 基于express+TS+mysql+sequelize的后端开发环境搭建
  • Go语言的移动应用测试
  • uniapp-x 子组件样式覆盖
  • 【推荐项目】052-用水监控管理系统
  • MAC地址IP地址如何转换?