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

数组-二分查找

目录

算法思想:

实践:

备注:


二分查找是一种高效的查找算法,适用于在 有序数组 或列表中快速定位目标元素的索引。

重要事情说三遍:使用前提:数组有序,无重复,如果数组未排序,先进行排序去重处理。

                                               数组有序,无重复,如果数组未排序,先进行排序去重处理。

                                               数组有序,无重复,如果数组未排序,先进行排序去重处理。        

算法思想:

  1. 初始化左右边界: 定义两个指针 leftright,分别指向数组的起始位置和终止位置。
  2. 计算中间位置: 根据公式 mid = left + (right - left) // 2 计算中间位置索引,避免大数相加可能导致的溢出。(mid=(left+right)/2)这种写法当left和right很大时,可能数据溢出。

实践:

二分查找中,容易写错的地方往往是边界条件区间的定义,这是导致程序混乱的根本原因。这里详细解释一下这两种常见的区间定义(左闭右闭左闭右开)及其实现逻辑。

左闭右闭:

#include <stdio.h>int binarySearch(int arr[], int size, int target) {int left = 0;int right = size - 1;while (left <= right) {// 使用向下取整的公式计算中点int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到目标值} else if (arr[mid] < target) {left = mid + 1; // 在右半部分查找} else {right = mid - 1; // 在左半部分查找}}return -1; // 未找到目标值
}int main() {int arr[] = {1, 3, 5, 7, 9, 11}; // 偶数长度数组int size = sizeof(arr) / sizeof(arr[0]);int target = 7;int result = binarySearch(arr, size, target);if (result != -1) {printf("目标值 %d 的索引是 %d\n", target, result);} else {printf("目标值 %d 未找到。\n", target);}return 0;
}

左闭右开:

#include <stdio.h>int search(int* nums, int numsSize, int target) {int left = 0;int right = numsSize; // 左闭右开区间while (left < right) { // 循环条件:left < rightint mid = left + (right - left) / 2;if (nums[mid] == target) {return mid; // 找到目标值} else if (nums[mid] > target) {right = mid; // 调整右边界} else {left = mid + 1; // 调整左边界}}return -1; // 未找到目标值
}int main() {int nums[] = {1, 3, 5, 7, 9};int numsSize = sizeof(nums) / sizeof(nums[0]);int target = 7;int result = search(nums, numsSize, target);if (result != -1) {printf("目标值 %d 的索引是 %d\n", target, result);} else {printf("目标值 %d 未找到。\n", target);}return 0;
}

备注:

在二分查找中,左中点(向下取整)右中点(向上取整) 的计算方式会影响算法的细节,但在实际应用中,它们的功能基本是等效的。

相关文章:

数组-二分查找

目录 算法思想&#xff1a; 实践&#xff1a; 备注&#xff1a; 二分查找是一种高效的查找算法&#xff0c;适用于在 有序数组 或列表中快速定位目标元素的索引。 重要事情说三遍&#xff1a;使用前提&#xff1a;数组有序&#xff0c;无重复&#xff0c;如果数组未排序&am…...

如何使用 Python 进行文件读写操作?

大家好&#xff0c;我是 V 哥。今天的内容来介绍 Python 中进行文件读写操作的方法&#xff0c;这在学习 Python 时是必不可少的技术点&#xff0c;希望可以帮助到正在学习 python的小伙伴。 以下是 Python 中进行文件读写操作的基本方法&#xff1a; 一、文件读取&#xff1…...

springcloud中的Feign调用

目录 一、基础应用 1.feign使用 1.增加feign依赖 2.编写feign接口 3.启用feign 4.调试 5.可能出现的异常信息 1.404 可能原因: 2.503 可有原因: 2.feign自定义配置 1.创建Feign配置类 2.feign接口 3.调试结果 3.feign多参数请求 Feign是Netflix开发的声明…...

【部署】将项目部署到云服务器

目录 1.获得服务器 2.连接到云服务器 3.配置环境 3.1.Java&#xff08;运行后端所需&#xff09; 3.2.MySQL数据库 3.3.Nginx&#xff08;运行前端所需&#xff09; 3.4. Node.js&#xff08;构建前端所需&#xff09; 4.打包项目 4.1.打包后端项目 4.2.打包前端项目…...

2024年AI大模型技术年度总结与应用实战:创新与突破并进

前言 回顾2024年&#xff0c;我一共发布了286篇博文&#xff0c;粉丝数也达到了43000多。这一年里&#xff0c;我收获颇丰&#xff0c;始终坚持AI大模型的研究方向&#xff0c;并且积极开展大模型的实战应用&#xff0c;也取得了一系列令人振奋的突破。 在286篇博文中&#…...

docker离线安装及部署各类中间件(x86系统架构)

前言&#xff1a;此文主要针对需要在x86内网服务器搭建系统的情况 一、docker离线安装 1、下载docker镜像 https://download.docker.com/linux/static/stable/x86_64/ 版本&#xff1a;docker-23.0.6.tgz 2、将docker-23.0.6.tgz 文件上传到服务器上面&#xff0c;这里放在…...

SuperdEye:一款基于纯Go实现的间接系统调用执行工具

关于SuperdEye SuperdEye是一款基于纯Go实现的间接系统调用执行工具&#xff0c;该工具是TartarusGate 的修订版&#xff0c;可以利用Go来实现TartarusGate 方法进行间接系统调用。 该工具的目标是为了扫描挂钩的NTDLL并检索Syscall编号&#xff0c;然后使用它来执行间接系统调…...

PCL 新增自定义点类型【2025最新版】

目录 一、自定义点类型1、前言2、定义方法3、代码示例二、合并现有类型三、点云按时间渲染1、CloudCompare渲染2、PCL渲染博客长期更新,本文最近更新时间为:2025年1月18日。 一、自定义点类型 1、前言 PCL库自身定义了很多点云类型,但是在使用的时候时如果要使用自己定义的…...

Docker导入镜像

使用命令行进行处理&#xff1a; docker load < onething1_wxedge.tar如下图所示 查看状态 docker images...

PyTorch使用教程(9)-使用profiler进行模型性能分析

1、简介 PyTorch Profiler是一个内置的性能分析工具&#xff0c;可以帮助开发者定位计算资源&#xff08;如CPU、GPU&#xff09;的瓶颈&#xff0c;从而更好地优化PyTorch程序。通过捕获和分析GPU的计算、内存和带宽利用情况&#xff0c;能够有效识别并解决性能瓶颈。 2、原…...

SpringBoot中使用MyBatis-Plus详细介绍

目录 一、MyBatis-Plus的使用步骤 1.引入MybatisPlus的起步依赖 2.定义Mapper&#xff08;也叫dao&#xff09;层的接口 3.MyBatis-Plus中常用注解 4. 使用MyBatis-Plus时要做如下配置 5.条件构造器 Wrapper 一、MyBatis-Plus的使用步骤 1.引入MybatisPlus的起步依赖 M…...

PCL 部分点云视点问题【2025最新版】

目录 一、问题概述二、解决方案1、软件实现2、代码实现三、调整之后博客长期更新,本文最近更新时间为:2025年1月18日。 一、问题概述 针对CloudCompare软件处理过的pcd格式点云,在使用PCL进行特征点提取、配准等实验中最终显示结果出现点云位置偏差较大的问题,本博客给出解…...

【Linux】常见指令(三)

Linux常见指令 01.nano02.cat03.cp04.mv 我的Linux专栏&#xff1a;【Linux】 本节Linux指令讲解的基本框架如下&#xff1a; 大家可以根据自己的需求&#xff0c;自行进行跳转和学习&#xff01; 01.nano nano Linux 系统中一款简单易用的命令行文本编辑器&#xff0c;适合…...

第5章:Python TDD定义Dollar对象相等性

写在前面 这本书是我们老板推荐过的&#xff0c;我在《价值心法》的推荐书单里也看到了它。用了一段时间 Cursor 软件后&#xff0c;我突然思考&#xff0c;对于测试开发工程师来说&#xff0c;什么才更有价值呢&#xff1f;如何让 AI 工具更好地辅助自己写代码&#xff0c;或许…...

nuxt3项目打包部署到服务器后配置端口号和开启https

nuxt3打包后的项目部署相对于一般vite打包的静态文件部署要稍微麻烦一些&#xff0c;还有一个主要的问题是开发环境配置的.env环境变量在打包后部署时获取不到&#xff0c;具体的解决方案可以参考我之前文章 nuxt3项目打包后获取.env设置的环境变量无效的解决办法。 这里使用的…...

MongoDB文档查询

一、实验目的 1. 理解MongoDB文档数据库的基本概念和特性。 2. 掌握在MongoDB中创建集合和插入文档数据的方法。 3. 学习使用MongoDB进行文档查询操作&#xff0c;包括查询、过滤和排序等。 二、实验环境准备 1. JAVA环境准备&#xff1a;确保Java Development Kit (J…...

【GORM】初探gorm模型,字段标签与go案例

GORM是什么&#xff1f; GORM 是一个Go 语言 ORM&#xff08;对象关系映射&#xff09;库&#xff0c;它让我们可以使用结构体来操作数据库&#xff0c;而无需编写SQL 语句 GORM 模型与字段标签详解 在 GORM 中&#xff0c;模型是数据库表的抽象表示&#xff0c;字段标签&am…...

Windows下的Milvus安装秘籍:向量数据库轻松上手

目录 一、简介 二、dockers的安装 1.介绍 2.环境准备 1.启动WSL 的功能。 2.安装并启动Hyper-V Windows10下的安装办法&#xff1a; Windows11下的安装办法&#xff1a; 启动Hyper-V 3.Docker的安装 4、验证是否安装成功 三、安装Milvus 1.Milvus下载 2.Milvus启动…...

在GUI中添加一个Label

标签是一种非常简单的小部件,它可以为我们的图形用户界面(GUI)增添价值。它可以阐释其他组件的用途,提供一些额外的信息,这可以引导用户理解输入框组件的含义,也能够解释那些无需用户输入数据的组件所显示数据的含义。 准备就绪 我们将扩展第一个应用案例,即《创建第一…...

hive连接mysql报错:Unknown version specified for initialization: 3.1.0

分享下一些报错的可能原因吧 1.要开启hadoop 命令&#xff1a;start-all.sh 2.检查 hive-site.xml 和 hive-env.sh。 hive-site.xml中应设置自己mysql的用户名和密码 我的hive-site.xml如下&#xff1a; <configuration><property><name>javax.jdo.opt…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...