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

【刷题笔记】--二分查找binarysearch

当给一个有序的数组,在其中查找某个数,可以考虑用二分查找。


题目1: 

二分查找的思路: 

设置left和right指针分别指向要查找的区间。mid指针指向这个区间的中间。比较mid指针所指的数与target。

如果mid所指的数小于target,那么就可以排除mid左边的所有数,left移向mid的右边一位,改变要查找的区间。

如果mid所指的数大于target,那么就可以排除mid右边的所有数,right移向mid的左边一位,改变要查找的区间。

代码:

int search(int* nums, int numsSize, int target){int left=0;int right=numsSize-1;int mid=(right+left)/2;while(left<=right){if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid-1;}else{return mid;}mid=(right+left)/2;}return -1;
}

 题目2:

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1:


输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出:true

思路: 

这个二维数组从左到右和从上到下都是有序的,这可以就可以想到用二分查找。

可以进行一行一行的二分查找即可。

代码:

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){int i;for(i=0;i<matrixSize;i++){int left=0;int right=(*matrixColSize)-1;while(left<=right){int mid=(left+right)/2;if(matrix[i][mid]<target){left=mid+1;}else if(matrix[i][mid]>target){right=mid-1;}else{return true;}}}return false;
}

相关文章:

【刷题笔记】--二分查找binarysearch

当给一个有序的数组&#xff0c;在其中查找某个数&#xff0c;可以考虑用二分查找。 题目1&#xff1a; 二分查找的思路&#xff1a; 设置left和right指针分别指向要查找的区间。mid指针指向这个区间的中间。比较mid指针所指的数与target。 如果mid所指的数小于target&…...

Python版本的常见模板(二) 数论(一)

文章目录前言质数相关质数判断求约数求取区间质数埃氏筛法线性筛法分解质因数欧拉欧拉函数求取单个数线性筛法求取欧拉定理求逆元快速幂/幂取模欧几里得算法求最小公约数拓展欧几里得算法求解同余方程前言 本文主要是提供Python版本的常见的一些与数论相关的模板&#xff0c;例…...

SQL快速上手(知识点总结+训练资料)

文章目录一 SQL训练资料二 SQL知识点总结1.SQL语句的执行顺序2.窗口函数3.字符串处理函数模糊查询三 SQL题目的总结一 SQL训练资料 牛客SQL题目 猴子数据分析题目 关注的公众号 猴子数据分析 二 SQL知识点总结 1.SQL语句的执行顺序 每一个子句产生的中间结果供接下来的子句…...

无需经验的steam搬砖,每天操作1小时,轻松创业赚钱!

我作为一个95后社畜&#xff0c;就喜欢倒腾各种赚钱的事情&#xff0c;8年老韭菜告诉你&#xff0c;副业创收一点都不难&#xff0c;难就难在是否找对项目&#xff0c;俗话说方向不对&#xff0c;努力白费&#xff01; 什么做苦力、技能、直播卖货&#xff0c;电商等等对比我这…...

如何创建你的公司的FAQ页面?

很多企业考虑为公司搭建一个“常见问题”页面&#xff0c;作为帮助客户回答关于产品和服务的常见问题的一种方式。 FAQ页面和登录/销售页面不同&#xff0c;没有展现出直接的投资回报&#xff0c;但是为团队节省了其他成本&#xff0c;据了解&#xff0c;高达67%的客户相比于跟…...

CK-GW06-E03与欧姆龙PLC配置指南

CK-GW06-E03与欧姆龙PLC配置指南CK-GW06-E03是一款支持标准工业EtherCAT协议的网关控制器,方便用户集成到PLC等控制系统中。本控制器提供了网络 POE 供电和直流电源供电两种方式&#xff0c;确保用户在使用无POE供电功能的交换机时可采用外接电源供电&#xff1b;系统还集成了六…...

使用docker-compose部署RocketMQ5.0

简介&#xff1a;使用docker-compose部署rocketmq5.0。文中会介绍docker-compose版本以及需要注意的项第一步&#xff1a;进入hub.docker.com搜索rocketmq我们选择第一个&#xff0c;因为第一个是7个月前更新的&#xff0c;&#xff08;我看有很多博客使用的依旧是最下面的那种…...

嵌入式ARM设计编程(四) ARM启动过程控制

文章和代码已归档至【Github仓库&#xff1a;hardware-tutorial】&#xff0c;需要的朋友们自取。或者公众号【AIShareLab】回复 嵌入式 也可获取。 一、实验目的 &#xff08;1&#xff09; 掌握建立基本完整的ARM 工程&#xff0c;包含启动代码&#xff0c;C语言程序等&…...

企业维基都说好,今天我们来看看 wiki 软件的缺点有哪些?

企业维基企业wiki和内部知识库可能看起来是一回事——但它们实际上是非常不同的软件类型。也许您可能不知道你在寻找的是知识基础软件&#xff0c;还是wiki软件。 无论哪种方式&#xff0c;缺乏知识都是生产力的巨大瓶颈。事实上&#xff0c;未能分享知识是财富500强企业每年亏…...

08- 汽车产品聚类分析综合项目 (机器学习聚类算法) (项目八)

找出性价比较高的车 LabelEncoder: python:sklearn标签编码(LabelEncoder) sklearn.preprocessing.LabelEncoder的使用&#xff1a;在训练模型之前&#xff0c;通常都要对数据进行一定得处理。将类别编号是一种常用的处理方法&#xff0c;比如把类别“电脑”&#xff0c;“手机…...

揭开苹果供应链,如何将其命运与中国深度捆绑

前 言 诺基亚在2007年时拥有9亿用户&#xff0c;在手机市场上占据主导地位&#xff0c;福布斯在当时以“谁能赶上手机之王&#xff1f;”为标题刊登了一篇关于该公司的报道&#xff0c;与此同时&#xff0c;苹果公司推出了iPhone系列产品。16年后&#xff0c;苹果公司以充足的…...

Mybatis 之useGeneratedKeys注意点

一.例子 Order.javapublic class Order {private Long id;private String serial; }orderMapper.xml<?xml version"1.0" encoding"UTF-8"?> <!DOCTYPE mapper PUBLIC "-//mybatis.org/DTD Mapper 3.0" "http://mybatis.org/dtd…...

数据结构---时间复杂度

专栏&#xff1a;数据结构 个人主页&#xff1a;HaiFan. 专栏简介&#xff1a;开学数据结构&#xff0c;接下来会慢慢坑新数据结构的内容&#xff01;&#xff01;&#xff01;&#xff01; 时间复杂度前言1.算法效率1.1如何衡量一个算法的好坏1.2算法的复杂度2.时间复杂度2.1大…...

如何保证集合是线程安全的 ConcurrentHashMap如何实现高效地线程安全?

第10讲 | 如何保证集合是线程安全的? ConcurrentHashMap如何实现高效地线程安全&#xff1f; 我在之前两讲介绍了 Java 集合框架的典型容器类&#xff0c;它们绝大部分都不是线程安全的&#xff0c;仅有的线程安全实现&#xff0c;比如 Vector、Stack&#xff0c;在性能方面也…...

C++对象模型和this指针

成员变量和成员函数分开存储&#xff1a;基本概念&#xff1a;在C中&#xff0c;类内的成员变量和成员函数分开存储只有非静态成员变量才属于类的对象上每个空对象都会有一个独一无二的内存地址&#xff0c;所以&#xff0c;空对象占用内存空间的大小为1代码实现&#xff1a;#i…...

kubernetes教程 --Pod调度

Pod调度 在默认情况下&#xff0c;一个Pod在哪个Node节点上运行&#xff0c;是由Scheduler组件采用相应的算法计算出来的&#xff0c;这个过程是不受人工控制的。但是在实际使用中&#xff0c;这并不满足的需求&#xff0c;因为很多情况下&#xff0c;我们想控制某些Pod到达某…...

功率放大器科普知识(晶体管功率放大器的注意事项)

虽然功率放大器是电子实验室的常用仪器&#xff0c;但是很多人对于它却没有清晰的认识&#xff0c;下面就让安泰电子来为大家介绍功率放大器的科普内容以及使用注意事项&#xff0c;希望大家可以对功率放大器有清晰的认识。功率放大器可以把输入信号的功率放大&#xff0c;以满…...

CentOS 7转化系统为阿里龙蜥Anolis OS 7

转载&#xff1a;原社区CentOS 7迁移Anolis OS 7迁移手册 一、注意事项 Anolis OS 7生态上和依赖管理上保持跟CentOS7.x兼容&#xff0c;一键式迁移脚本centos2anolis.py&#xff0c;实现CentOS7.x到Anolis OS 7的平滑迁移。 使用迁移脚本前需要注意如下事项&#xff1a; 迁…...

【快速复习】一文看懂 Mysql 核心存储 隔离级别 锁 MVCC 机制

一文看懂 Mysql 核心存储 & 隔离级别 & 锁 & MVCC 机制 Mysql InnoDB 引擎下核心存储 数据&索引存储 IBD 文件 mysql 实际存储采用 B 树结构。 B 树是一种多路搜索树&#xff0c;其搜索性能高于 B 树 所有叶节点在同一深度&#xff0c;保证搜索效率仅叶节…...

面试题----集合

概述 从上图可以看出&#xff0c;在Java 中除了以 Map 结尾的类之外&#xff0c; 其他类都实现了 Collection 接⼝。 并且&#xff0c;以 Map 结尾的类都实现了 Map 接⼝List,Set,Map List (对付顺序的好帮⼿)&#xff1a; 存储的元素是有序的、可重复的。 Set (注重独⼀⽆⼆…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...