当前位置: 首页 > 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 (注重独⼀⽆⼆…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...