当前位置：首页 > news >正文

算法基础--二分查找

news 来源：原创 2025/5/15 5:58:24

模板

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map> 
/**
二分查找（Binary Search）是一种高效的查找算法，其时间复杂度为 o(logn) 
*/
using namespace std;const int N = 100010;int n, q, a[N];
unordered_map<int, int> m;int main() {scanf("%d%d", &n, &q);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);m[a[i]] = i; // 修正：将元素索引存入 unordered_map}while (q--) {int x;scanf("%d", &x);int R, L;int l = 0, r = n - 1;// 二分查找右边界while (l < r) {int mid = l + r + 1 >> 1;if (a[mid] <= x) {l = mid;} else {r = mid - 1;}}R = r; // 二分结束后，l 和 r 相同，共同指向边界 l = 0;r = n - 1;// 二分查找左边界while (l < r) {int mid = l + r >> 1; // 修正：正确计算 midif (a[mid] >= x) {r = mid;} else {l = mid + 1;}}L = r;if (m.find(x) != m.end()) { // 修正：正确判断元素是否存在cout << L << " " << R << endl;} else {cout << "-1 -1" << endl; // 若元素不存在，输出 -1 -1}}return 0;
}

优化（java)

/*** @author adwish* @description 整数二分，用于查询多个元素出现的位置
主要功能是对一个已排序的整数数组进行多次查询，每次查询一个整数 x，
并找出该整数在数组中首次出现和最后一次出现的位置，如果该整数不存在于数组中，则输出 -1 -1。* @date 2025-02-03 12:54*/
import java.util.Scanner;public class IntegerBinary {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取数组长度n和查询次数qint n = scanner.nextInt();int q = scanner.nextInt();// 定义数组并读取元素int[] a = new int[n];for (int i = 0; i < a.length; i++) {a[i] = scanner.nextInt();}// 进行查询for (int i = 0; i < q; i++) {int x = scanner.nextInt();int L = findLeftBound(a, x);int R = findRightBound(a, x);// 判断元素是否存在数组中if (L < R && R < n && a[L] == x && a[R] == x) {System.out.println(L + " " + R);} else {System.out.println("-1 -1");}}scanner.close();}// 查找左边界private static int findLeftBound(int[] a, int x) {int l = 0, r = a.length - 1;while (l < r) {int mid = (l + r) / 2;if (a[mid] >= x) {r = mid;} else {l = mid + 1;}}return l;}// 查找右边界private static int findRightBound(int[] a, int x) {int l = 0, r = a.length - 1;while (l < r) {int mid = (l + r + 1) / 2;  // 防止死循环if (a[mid] <= x) {l = mid;} else {r = mid - 1;}}return l;}
}

练习案例

题目描述35. 搜索插入位置https://leetcode.cn/problems/search-insert-position/

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 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 target) {int l = 0, r = nums.size() - 1;while(l <= r){int mid = l + (r - l)  / 2;//计算中间值的推荐方式，防止溢出if(nums[mid] == target){return mid;}else if(nums[mid] < target){
l = mid + 1;} else{r = mid - 1;}}return l;}};

题目描述

69. x 的平方根 https://leetcode.cn/problems/sqrtx/

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去

一般解法：

class Solution {
public:int mySqrt(int x) {if (x == 0 || x == 1) return x; // 边界条件int left = 0, right = x;int result = 0;while (left <= right) {int mid = left + (right - left) / 2;if (mid <= x / mid) { // 避免 mid * mid 溢出result = mid;     // 更新结果left = mid + 1;   // 搜索右半部分} else {right = mid - 1;  // 搜索左半部分}}return result;}};

牛顿迭代法

class Solution {int s;public int mySqrt(int x) {s=x;if(x==0) return 0;return ((int)(sqrts(x)));}public double sqrts(double x){double res = (x + s / x) / 2;if (res == x) {return x;} else {return sqrts(res);}} 
}

数的三次方根（精确）

模板

#include<bits/stdc++.h>using namespace std;double n = 0;int main(){cin >> n;double  l = -50, r = 50;while( r - l >= 1e-8)//使l和r精确到1e-6，?要求的多两位，常识！！{double mid = (l + r) / 2;if(mid * mid * mid >= n) r = mid;else l = mid; }printf("%.6f" ,l);return 0;}

算法基础--二分查找

模板 #include <iostream> #include <cstring> #include <algorithm> #include <unordered_map> /** 二分查找（Binary Search）是一种高效的查找算法，其时间复杂度为 o(logn) */ using namespace std;const int N …...

编程日记 2025/5/15 5:58:24

Vue 3 30天精进之旅：Day 14 - 项目实践

在前面的学习中，我们已经掌握了Vue 3的基础知识，包括其核心概念、Vue Router、Vuex，以及异步操作等。今天是一个重要的里程碑：我们将把这些知识整合到一个实际的项目中。通过项目实践，你将能够深入理解所学知识&#x…...

编程日记 2025/5/15 7:30:14

【Java基础-42.4】Java中的包装类对象默认值：深入解析与注意事项

在Java编程中，包装类（Wrapper Classes）是将基本数据类型（如int、char等）封装为对象的类。它们提供了更多的功能和灵活性，例如允许基本数据类型参与面向对象的操作（如存储在集合中）。…...

编程日记 2025/5/15 7:53:10

Linux进程概念

目录一.进程二.进程状态三.环境变量四.程序地址空间五.Linux2.6内核进程调度队列一.进程基本概念课本概念：程序的一个执行实例，正在执行的程序等内核观点：担当分配系统资源（CPU时间，内存）的…...

编程日记 2025/5/15 7:40:02

Linux的简单使用和部署4asszaaa0

一.部署 1 环境搭建方式主要有四种: 1. 直接安装在物理机上.但是Linux桌面使用起来非常不友好.所以不建议.[不推荐]. 2. 使用虚拟机软件,将Linux搭建在虚拟机上.但是由于当前的虚拟机软件(如VMWare之类的)存在⼀些bug,会导致环境上出现各种莫名其妙的问题比较折腾.[非常不推荐…...

编程日记 2025/5/15 7:24:41

人工智能专业术语详解（A）

人工智能不仅是指寻求如何替代人类的机器人或人类寻求自我挑战的游戏，更是指运用复杂的程序化数学，其结果与高质量的训练数据相结合，推动了我们在日常生活中所看到的技术进步。从无人驾驶汽车到寻找癌症的治疗方法，人工智能正在逐…...

编程日记 2025/5/15 4:43:38

深度学习 Pytorch 基础网络手动搭建与快速实现

为了方便后续练习的展开，我们尝试自己创建一个数据生成器，用于自主生成一些符合某些条件、具备某些特性的数据集。导入相关的包 # 随机模块 import random# 绘图模块 import matplotlib as mpl import matplotlib.pyplot as plt# 导入numpy import nu…...

编程日记 2025/5/15 7:18:36

deepseek的对话风格

概述 deepseek的对话风格，比一般的模型的回答多了思考过程，这是它比较可爱的地方，模型的回答有了思考过程，对用户而言大模型的回答不完全是一个黑盒。 deepseek的对话风格 train_prompt_style """Below is an…...

编程日记 2025/5/13 12:22:45

Spring Security(maven项目) 3.0.2.9版本 --- 改

前言： 通过实践而发现真理，又通过实践而证实真理和发展真理。从感性认识而能动地发展到理性认识，又从理性认识而能动地指导革命实践，改造主观世界和客观世界。实践、认识、再实践、再认识，这种形式，循环往…...

编程日记 2025/5/13 5:04:46

OpenAI新商标申请曝光：AI硬件、机器人、量子计算全线布局？

每周跟踪AI热点新闻动向和震撼发展想要探索生成式人工智能的前沿进展吗？订阅我们的简报，深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同，从行业内部的深度分析和实用指南中受益。不要错过这个机会，成为AI领…...

编程日记 2025/5/12 11:19:51

TVM调度原语完全指南：从入门到微架构级优化

调度原语在TVM的抽象体系中，调度（Schedule）是对计算过程的时空重塑。每一个原语都是改变计算次序、数据流向或并行策略的手术刀。其核心作用可归纳为： 优化目标 max ⁡ ( 计算密度内存延迟指令开销 ) \text{优化目标} \max…...

编程日记 2025/5/14 22:10:26

题目：ImageNet Classification with Deep Convolutional Neural Networks 发文机构：多伦多大学作者：Alex Krizhevsky，Ilya Sutskever，Geoffrey E. Hinton（人工智能教父，AI三巨头——杰弗里.辛顿（Geoffrey Hinton），约书亚.本吉奥（Yoshua Bengio）和扬.勒丘恩（Yan…...

编程日记 2025/5/13 5:40:37

Starrocks 对比 Clickhouse

极速查询的单表查询 StarRocks 在极速查询方面上做了很多，下面着重介绍四点： 1）向量化执行：StarRocks 实现了从存储层到查询层的全面向量化执行，这是 StarRocks 速度优势的基础。向量化执行充分发挥了 CPU 的处理能力…...

编程日记 2025/5/13 10:56:20

C++实现一款功能丰富的通讯录管理系统

在学习编程的过程中，如何设计一个实用的项目是许多同学头疼的问题。如果你是一位正在学习C的同学，想通过实际项目巩固知识，那么这个通讯录管理系统绝对是一个理想的练手项目。在本文中，我将详细拆解代码逻辑，帮助你理解…...

编程日记 2025/5/11 22:22:16

动态规划之背包问题

文章目录 0-1 背包问题1. 二维动态规划实现（0-1 背包）：2. 一维动态规划实现（0-1 背包）： 完全背包问题1. 二维动态规划实现（完全背包）：2. 一维动态规划实现（完…...

编程日记 2025/5/13 7:41:02

Linux抢占式内核：技术演进与源码解析

一、引言 Linux内核作为全球广泛使用的开源操作系统核心，其设计和实现一直是计算机科学领域的研究热点。从早期的非抢占式内核到2.6版本引入的抢占式内核，Linux在实时性和响应能力上取得了显著进步。本文将深入探讨Linux抢占式内核的引入背景、技术实现以及与非抢占式内核的…...

编程日记 2025/5/14 9:29:23

Rust语言进阶之文件处理：BufWriter用法实例(一百零四)

简介： CSDN博客专家、《Android系统多媒体进阶实战》一书作者新书发布：《Android系统多媒体进阶实战》🚀 优质专栏： Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏： 多媒体系统工程师系列【…...

编程日记 2025/5/12 8:02:04

EtherCAT主站IGH-- 30 -- IGH之master.h/c文件解析

EtherCAT主站IGH-- 30 -- IGH之master.h/c文件解析 0 预览一该文件功能`master.c` 文件功能函数预览二函数功能介绍`master.c` 中主要函数的作用1. `ec_master_init`2. `ec_master_clear`3. `ec_master_thread_start`4. `ec_master_thread_stop`5. `ec_master_enter_idle_pha…...

编程日记 2025/5/15 7:42:13

关于deepseek的一些普遍误读

最近deepseek成为全球最热门的话题，甚至没有之一，无论是北美，欧洲，各大IT巨头，各个投资机构，政府官员，乃至脱口秀演员，都在不断提及这个话题，而国内，自媒体也…...

编程日记 2025/5/14 14:06:13

刷题记录动态规划-7: 63. 不同路径 II

题目：63. 不同路径 II 难度：中等给定一个 m x n 的整数数组 grid。一个机器人初始位于左上角（即 grid[0][0]）。机器人尝试移动到右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。…...

编程日记 2025/5/15 5:37:36

7-2 拯救外星人

7-2 拯救外星人你的外星人朋友不认得地球上的加减乘除符号，但是会算阶乘 —— 正整数 N 的阶乘记为 “N!”，是从 1 到 N 的连乘积。所以当他不知道“57”等于多少时，如果你告诉他等于“12!”，他就写出了“479001600”这个答案。…...

编程日记 2025/5/15 3:58:31

人工智能导论-第3章-知识点与学习笔记

参考教材3.2节的内容，介绍什么是自然演绎推理；解释“肯定后件”与“否定前件”两类错误的演绎推理是什么意义，给出具体例子加以阐述。参考教材3.3节的内容，介绍什么是文字（literal）；介绍什么是子…...

编程日记 2025/5/14 6:59:57

一个开源 GenBI AI 本地代理（确保本地数据安全），使数据驱动型团队能够与其数据进行互动，生成文本到 SQL、图表、电子表格、报告和 BI

一、GenBI AI 代理介绍（文末提供下载） github地址：https://github.com/Canner/WrenAI 本文信息图片均来源于github作者主页在 Wren AI，我们的使命是通过生成式商业智能 （GenBI） 使组织能够无缝访问数据&…...

编程日记 2025/5/12 3:21:44

Java 大视界 -- Java 大数据在智能电网中的应用与发展趋势（71）

💖亲爱的朋友们，热烈欢迎来到青云交的博客！能与诸位在此相逢，我倍感荣幸。在这飞速更迭的时代，我们都渴望一方心灵净土，而我的博客正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识，也…...

编程日记 2025/5/13 5:02:16

c语言练习题【消息队列、共享内存、信号灯集】

练习1:消息队列请使用消息队列实现2个终端之间互相聊天 #发送端 key_t key; int id;typedef struct Msgbuf{long channel;char buf[128];}msg_t;int main(int argc, const char *argv[]) {if (argc<2){printf("传入频道号\n");return 1;}keyftok("./ipc&q…...

编程日记 2025/5/12 6:30:46

力扣 295. 数据流的中位数

🔗 https://leetcode.cn/problems/find-median-from-data-stream/ 题目数据流中不断有数添加进来，add 表示添加数据，find 返回数据流中的中位数思路大根堆存储数据流中偏小的数据小根堆存储数据流中偏大的数据若当前的 num 比大根堆的…...

编程日记 2025/5/10 11:01:10

JavaScript原型链与继承：优化与扩展的深度探索

在 JavaScript 的世界里，万物皆对象，而每个对象都有一个与之关联的原型对象，这就构成了原型链的基础。原型链，简单来说，是一个由对象的原型相互连接形成的链式结构。每个对象都有一个内部属性[[Prototype]]&#xff0…...

编程日记 2025/5/13 6:07:53

【建站】专栏目录

建站专栏的想法有很多，想写穷鬼如何快速低成本部署前后端项目让用户能访问到，如何将网站收录到百度，bing，google并优化seo让搜索引擎搜索到网站，想写如何把网站加入google广告或者接入stripe信用卡首款平台收款&#x…...

编程日记 2025/5/15 7:09:58

题目 1160: 出圈

题目描述设有n个人围坐一圈并按顺时针方向从1到n编号，从第1个人开始进行1到m的报数，报数到第个m人，此人出圈，再从他的下一个人重新开始1到m的报数，如此进行下去直到所剩下一人为止。输入格式输入多行，每…...

编程日记 2025/5/14 9:29:19

Python小游戏29乒乓球

import pygame import sys # 初始化pygame pygame.init() # 屏幕大小 screen_width 800 screen_height 600 screen pygame.display.set_mode((screen_width, screen_height)) pygame.display.set_caption("打乒乓球") # 颜色定义 WHITE (255, 255, 255) BLACK (…...

编程日记 2025/5/13 8:46:27

力扣【99. 恢复二叉搜索树】Java题解(二叉树的 Morris 遍历)

题目链接 Morris遍历递归和迭代遍历，不管是前序中序还是后续，空间复杂度都是O(n)（递归是因为隐式调用栈的开销）。而Morris遍历可以做到空间复杂度是O(1)。思路就是节点的前序节点的右指针指向该节点，来保证可以通…...

编程日记 2025/5/14 17:19:02

CNN的各种知识点（一）：卷积神经网络CNN通道数的理解！

卷积神经网络CNN通道数的理解！ 通道数的核心概念解析1. 通道数的本质 2. 单张灰度图的处理示例： 3. 批量输入的处理通道与批次的关系： 4. RGB三通道输入的处理计算过程：示例： 5. 通道数的实际意义6. 可视化理解(1) 单通…...

编程日记 2025/5/12 10:26:53

python-UnitTest框架笔记

UnitTest框架的基本使用方法 UnitTest框架介绍框架：framework，为了解决一类事情的功能集合 UnitTest框架：是python自带的单元测试框架自带的，可以直接使用，不需要格外安装测试人员用来做自动化测试，作…...

编程日记 2025/5/11 7:33:21

书生大模型实战营3

文章目录 L0——入门岛git基础Git 是什么？Git 中的一些基本概念工作区、暂存区和 Git 仓库区文件状态分支主要功能 Git 平台介绍GitHubGitLabGitee Git 下载配置验证下载 Git配置 Git验证 Git配置 Git常用操作Git简易入门四部曲Git其他指令闯关任务任务1: 破冰活动…...

编程日记 2025/5/14 5:29:26

在CentOS服务器上部署DeepSeek R1

在CentOS服务器上部署DeepSeek R1，并通过公网IP与其进行对话，可以按照以下步骤操作：一、环境准备系统要求： CentOS 8+（需支持AVX512指令集）。硬件配置： GPU版本：NVIDIA驱动520+，CUDA 11.8+。 CPU版本：至少16核处理器，64GB内存。存储空间：原始模型需要30GB，量…...

编程日记 2025/5/14 12:38:54

C++中常用的十大排序方法之4——希尔排序

成长路上不孤单😊😊😊😊😊😊 【😊///计算机爱好者😊///持续分享所学😊///如有需要欢迎收藏转发///😊】今日分享关于C中常用的排序方法之4——希尔排序的相…...

编程日记 2025/5/14 5:45:27

机器学习day7

自定义数据集使用pytorch框架实现逻辑回归并保存模型，然后保存模型后再加载模型进行预测，对预测结果计算精确度和召回率及F1分数代码 import numpy as np import torch import torch.nn as nn import torch.optim as optimizer import matplotlib.pyp…...

编程日记 2025/5/14 11:02:36

【流媒体】搭建流媒体服务器

搭建Windows Nginx服务器搭建下载nginx工具包解压至本地，并在cmd窗口中切换至nginx所在的本地目录修改 conf/nginx.conf 文件，更改其端口号 server中的 listen的端口号从 80改为 8080，因为80经常被其他服务占用，导致无法打开 …...

编程日记 2025/5/12 21:27:20

（电脑版）植物大战僵尸幼儿园版本，开启你的冒险之旅！

欢迎来到植物大战僵尸中文版，园长Jen已准备好迎接你的挑战！在这个充满乐趣和策略的游戏中，你将体验到多种游戏模式，每种模式都带来不同的挑战和乐趣。游戏模式： 冒险模式：踏上刺激的冒险旅程，…...

编程日记 2025/5/14 10:20:41

民法学学习笔记(个人向) Part.2

民法学学习笔记(个人向) Part.2 民法始终在解决两个生活中的核心问题： 私法自治；交易安全； 3. 自然人 3.4 个体工商户、农村承包经营户都是特殊的个体经济单位； 3.4.1 个体工商户是指在法律的允许范围内，依法经…...

编程日记 2025/5/10 11:00:50

解决SetWindowCompositionAttribute使控件文本透明的问题

用以下参数调用该API，能实现类似Aero的模糊透明效果。参数具体含义见 https://zhuanlan.zhihu.com/p/569258181 http://www.memotech.de/WindowComposition/Text.txt http://www.memotech.de/WindowComposition/WindowComposition.zip DWORD accent[4] { 3,0,0,0 …...

编程日记 2025/5/14 10:21:02

响应式编程与协程

响应式编程与协程的比较响应式编程的弊端虚拟线程Java线程内核线程的局限性传统线程池的demo虚拟线程的demo 响应式编程的弊端前面用了几篇文章介绍了响应式编程，它更多的使用少量线程实现线程间解耦和异步的作用，如线程的Reactor模型，主要…...

编程日记 2025/5/9 14:33:06

Altium Designer绘制原理图时画斜线的方法

第一步：检查设置是否正确打开preferences->PCB Editor ->Interactive Routing->Interactive Routing Options->Restrict TO 90/45去掉勾选项，点击OK即可。如下图所示： 然后在划线时，按下shift空格就能够切换划线…...

编程日记 2025/5/12 22:28:45

Android --- CameraX讲解

预备知识 surface surfaceView SurfaceHolder surface 是什么？ 一句话来说： surface是一块用于填充图像数据的内存。 surfaceView 是什么？ 它是一个显示surface 的View。在app中仍在 ViewHierachy 中，但在wms 中可以理解为…...

编程日记 2025/5/10 11:00:47

动态分库分表

1. 动态分库分表的核心目标解决单库性能瓶颈：通过水平拆分数据，提升并发处理能力。支持弹性扩展：在不中断服务的前提下，实现数据分片的动态扩容/缩容。避免跨分片操作：减少跨分片查询（如JOIN、事务&am…...

编程日记 2025/5/11 12:54:39

shell -c

个人博客地址：shell -c | 一张假钞的真实世界 shell -c {string}：表示命令从-c后的字符串读取。在需要使用管道或者重定向需要sudo时很有用，如下： $ sudo find ../*/exportFiles -mtime 15 -name "*" | xargs -I {} r…...

编程日记 2025/5/12 19:56:33

Spring Boot 2 快速教程：WebFlux处理流程（五）

WebFlux请求处理流程下面是spring mvc的请求处理流程具体步骤： 第一步：发起请求到前端控制器(DispatcherServlet) 第二步：前端控制器请求HandlerMapping查找 Handler （可以根据xml配置、注解进行查找） 匹配条件包括…...

编程日记 2025/5/12 11:19:47

10.8 LangChain Output Parsers终极指南：从JSON解析到流式处理的规范化输出实践

LangChain Output Parsers终极指南：从JSON解析到流式处理的规范化输出实践关键词： LangChain Output Parsers、结构化输出、JSON解析、数据校验、流式处理一、为什么需要规范化输出？大模型输出的“荒野西部”问题原始输出的三大痛点：格式不可控：模型可能返回纯文本、…...

编程日记 2025/5/12 22:28:40