首页 > 编程语言 >基础二分算法:整数二分、浮点二分

基础二分算法:整数二分、浮点二分

时间:2023-09-16 20:34:05浏览次数:43  
标签:二分 int double mid 整数 浮点 算法

1、整数二分

以acwing 789为例,题目要求如下:

第一行输入整数n和q,表示数组长度和询问个数。

第二行输入数组,包含n个整数。

接下来q行,每一行一个整数k,表示一个问询元素。

要求输出q行,每行包含两个整数,表示所求元素的起始位置和终止位置。

如果数组中不存在该元素,则返回 -1 -1。

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n, m, q[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    while (m--) {
        int x;
        scanf("%d", &x);

        //寻找第一个满足条件的值
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }

        if (q[l] != x) cout << "-1 -1" << endl;
        else {
            cout << l << ' ';

            //寻找最后一个满足条件的值
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }

            cout << l << endl;
        }
    }
}

 

2、浮点二分

浮点二分需要确定精度,但不需要和整数二分一样做加1减1的边缘判断。

以求根号为例,

要求输入一个double值,返回其算术平方根,要求精度保留四位小数。

#include <iostream>
using namespace std;

int main() {
    double x;
    cin >> x;
    
    double l = 0, r = x;
    while (r - l > 1e-6) {
        double mid = (l + r) / 2; 
        if (mid * mid >= x) r = mid; 
        else l = mid;
    }

    printf("%lf", l);

    return 0;
}

 

标签:二分,int,double,mid,整数,浮点,算法
From: https://www.cnblogs.com/karinto/p/17707255.html

相关文章

  • 算法刷题:DP专题(9.16,持续更)
    算法刷题系列上期:递归、栈/队列、树、回溯、DP(8.29)数组指针、前缀和/差分/树状数组、滑窗/单调队列/滚动哈希、二分(8.13)链表题(8.29)目录动态规划基础状态状态转移函数题目三角形最小路径和动态规划基础状态状态转移函数题目三角形最小路径和时间:3ms击败77%class......
  • 计算机视觉算法中的双眼视觉(Binocular Vision)
    引言双眼视觉是人类视觉系统中重要的特征之一,它使我们能够感知到三维空间中的深度和距离。在计算机视觉领域,双眼视觉被广泛应用于目标检测、立体视觉、人脸识别等任务中。本文将介绍双眼视觉的原理和在计算机视觉算法中的应用。双眼视觉原理双眼视觉是指人类使用两只眼睛同时观察同......
  • 基于间隔密度的概念漂移检测算法mdm-DDM
    概念漂移​ 概念漂移是数据流挖掘领域中一个重要的研究点。传统的机器学习算法在操作时通常假设数据是静态的,其数据分布不会随着时间发生变化。然而对于真实的数据流来说,由于数据流天生的时间性,到达的数据的分布可能会随着时间的推移不断改变。这使得传统的批处理模型不适合对数......
  • 基础算法:快速排序、归并排序
    1、快速排序#include<iostream>usingnamespacestd;constintN=1e5+10;intn,q[N];voidqksort(intq[],intl,intr){if(l>=r)return;intx=q[l],i=l-1,j=r+1;while(i<j){doi++;while(q[i]<......
  • java递归算法
    当解决问题时,递归是一种常用而强大的算法技术。在Java中,递归是指方法调用自身的过程。它可以用于解决许多问题,特别是与算法和数据结构有关的问题。在本博客中,我们将详细介绍Java中的递归算法,并提供一些具体的代码示例。什么是递归?递归的基本概念和特点递归是指方法在其定义中......
  • 代码随想录算法训练营第十天
    代码随想录算法训练营第十天|LeetCode20(有效的括号)LeetCode1047(删除字符串中的所有相邻重复项)LeetCode150(逆波兰表达式求值)20:有效的括号LeetCode20(有效的括号)方法一importjava.util.Stack;classSolution{publicbooleanisValid(Strings){......
  • tortoise-orm 使用雪花算法生成主键ID
    importtimefromtortoiseimportTortoise,fields,run_asyncfromtortoise.modelsimportModelfromtypingimportAnyclassSnowflake:def__init__(self,machine_id:int):"""生成雪花算法ID:parammachine_id:机器ID......
  • # 二分法
    l.sort()defindex(l,target_num):iflen(l)==0:print('没找到')returnmiddle_index=len(l)//2ifl[middle_index]<target_num:l_right=l[middle_index+1:]re......
  • lecode算法题 小总结
    .......1打印9x9乘法表#python版foriinrange(1,10):forkinrange(1,i+1):print(f'{i}X{k}\t',end='')print('\n')------------------#c版#include<stdio.h>intmain(){inti;......
  • 机器学习算法原理实现——adaboost,三个臭皮匠顶个诸葛亮
    adaboost算法的基本原理是什么?举一个简单的例子说明呢 AdaBoost(AdaptiveBoosting)是一种集成学习方法,其基本原理是结合多个弱学习器来构建一个强学习器。AdaBoost的工作方式如下:权重初始化:给定一个训练数据集,首先为每个训练样本分配一个权重,开始时这些权......