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

算法总结-二分查找

文章目录

    • 1.搜索插入位置
        • 1.答案
        • 2.思路
    • 2.搜索二维矩阵
        • 1.答案
        • 2.思路
    • 3.寻找峰值
        • 1.答案
        • 2.思路
    • 4.搜索旋转排序数组
        • 1.答案
        • 2.思路
    • 5.在排序数组中查找元素的第一个和最后一个位置
        • 1.答案
        • 2.思路
    • 6.寻找旋转排序数组中的最小值
        • 1.答案
        • 2.思路

1.搜索插入位置

1.答案
package com.sunxiansheng.arithmetic.day18;/*** Description: 35. 搜索插入位置** @Author sun* @Create 2025/1/30 10:11* @Version 1.0*/
public class t35 {public static int searchInsert(int[] nums, int target) {// 左闭右闭,加等号int left = 0, right = nums.length - 1;while (left <= right) {// 求中点int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;}if (nums[mid] < target) {left = mid + 1;}if (nums[mid] > target) {right = mid - 1;}}// 如果找不到,就返回应该插入的位置return left;}
}
2.思路

左闭右闭,加等号,求中点,找不到就返回left

2.搜索二维矩阵

1.答案
package com.sunxiansheng.arithmetic.day18;/*** Description: 74. 搜索二维矩阵** @Author sun* @Create 2025/1/30 10:16* @Version 1.0*/
public class t74 {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;// 左闭右闭int left = 0, right = m * n - 1;// 加等号while (left <= right) {// 求中点int mid = left + (right - left) / 2;// 转换中点下标为二维数组的下标int i = mid / n;int j = mid % n;if (matrix[i][j] == target) {return true;}if (matrix[i][j] < target) {left = mid + 1;}else if (matrix[i][j] > target) {right = mid - 1;}}return false;}
}
2.思路

就是在求中点的时候有些不一样,需要将数字转换为二维数组的下标,公式就是x / n 和 x % n

3.寻找峰值

1.答案
package com.sunxiansheng.arithmetic.day18;/*** Description: 162. 寻找峰值** @Author sun* @Create 2025/1/30 10:35* @Version 1.0*/
public class t162 {public int findPeakElement(int[] nums) {// 左闭右闭加等号int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;// 判断是否大于左右边元素boolean leftSmaller = mid == 0 || nums[mid] > nums[mid - 1];boolean rightSmaller = (mid == nums.length - 1) || nums[mid] > nums[mid + 1];// 如果都大于,则当前元素就是峰值if (leftSmaller && rightSmaller) {return mid;}// 如果比左边的元素大,则峰值在右边if (leftSmaller) {left = mid + 1;} else {// 其余情况峰值在左边right = mid - 1;}}return -1;}
}
2.思路

除了二分老套路之外,还要判断是否大于左右边元素,如果都大于就是峰值,如果只是大于左边但是小于右边,那么峰值就在右边

4.搜索旋转排序数组

1.答案
package com.sunxiansheng.arithmetic.day18;/*** Description: 33. 搜索旋转排序数组** @Author sun* @Create 2025/1/30 11:05* @Version 1.0*/
public class t33 {public static int search(int[] nums, int target) {if (nums == null || nums.length == 0) {return -1;}// 左闭,右闭,加等号int left = 0, right = nums.length - 1;while (left <= right) {// 求中点int mid = left + (right - left) / 2;// 找到了就直接返回if (target == nums[mid]) {return mid;}// 找不到,如果左边是有序的if (nums[mid] >= nums[left]) {// 判断是否在左边if (target >= nums[left] && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}} else {// 目前是右边有序,则判断是否在右边if (target <= nums[right] && target > nums[mid]) {left = mid + 1;} else {right = mid - 1;}}}return -1;}
}
2.思路

左闭右闭加等号,求中点,如果找不到,就判断左边是不是有序的,如果左边有序,就进一步判断元素是否在左边,如果在就right = mid - 1,否则就是left = mid + 1,右边也是同理

5.在排序数组中查找元素的第一个和最后一个位置

1.答案
package com.sunxiansheng.arithmetic.day18;/*** Description: 34. 在排序数组中查找元素的第一个和最后一个位置** @Author sun* @Create 2025/1/30 11:23* @Version 1.0*/
public class t34 {public int[] searchRange(int[] nums, int target) {if (nums == null || nums.length == 0) {return new int[]{-1, -1};}return new int[]{getFirst(nums, target), getLast(nums, target)};}private int getFirst(int[] nums, int target) {// 左闭右闭,加等号int left = 0, right = nums.length - 1;while (left <= right) {// 求中点int mid = left + (right - left) / 2;if (target <= nums[mid]) {right = mid - 1;} else {left = mid + 1;}}// 防止越界if (left < 0 || left > nums.length - 1) {return -1;}return nums[left] == target ? left : -1;}private int getLast(int[] nums, int target) {// 左闭右闭,加等号int left = 0, right = nums.length - 1;while (left <= right) {// 求中点int mid = left + (right - left) / 2;if (target >= nums[mid]) {left = mid + 1;} else {right = mid - 1;}}// 防止越界if (right < 0 || right > nums.length - 1) {return -1;}return nums[right] == target ? right : -1;}
}
2.思路

以找到第一个元素为例,首先还是二分老套路,然后如果target小于等于mid的元素,就在左边,否则在右边,注意退出循环后要防止越界,并且最后返回的时候也要判断left下的元素是不是那个元素!

6.寻找旋转排序数组中的最小值

1.答案
package com.sunxiansheng.arithmetic.day18;/*** Description: 153. 寻找旋转排序数组中的最小值** @Author sun* @Create 2025/1/30 13:07* @Version 1.0*/
public class t153 {public int findMin(int[] nums) {// 左闭右闭加等号int left = 0, right = nums.length - 1;int res = nums[left];while (left <= right) {// 求中点int mid = left + (right - left) / 2;// 更新最小值res = Math.min(res, nums[mid]);// 将right指向的元素当做targetif (nums[mid] <= nums[right]) {right = mid - 1;} else  {left = mid + 1;}}return res;}
}
2.思路

在二分的基础上,加了一个更新最小值的操作,并且将right指向的元素当做target进行更新左右边界的操作

相关文章:

算法总结-二分查找

文章目录 1.搜索插入位置1.答案2.思路 2.搜索二维矩阵1.答案2.思路 3.寻找峰值1.答案2.思路 4.搜索旋转排序数组1.答案2.思路 5.在排序数组中查找元素的第一个和最后一个位置1.答案2.思路 6.寻找旋转排序数组中的最小值1.答案2.思路 1.搜索插入位置 1.答案 package com.sunxi…...

基于python的Kimi AI 聊天应用

因为这几天deepseek有点状况&#xff0c;导致apikey一直生成不了&#xff0c;用kimi练练手。这是一个基于 Moonshot AI 的 Kimi 接口开发的聊天应用程序&#xff0c;使用 Python Tkinter 构建图形界面。 项目结构 项目由三个主要Python文件组成&#xff1a; 1. main_kimi.py…...

动手学深度学习-3.2 线性回归的从0开始

以下是代码的逐段解析及其实际作用&#xff1a; 1. 环境设置与库导入 %matplotlib inline import random import torch from d2l import torch as d2l作用&#xff1a; %matplotlib inline&#xff1a;在 Jupyter Notebook 中内嵌显示 matplotlib 图形。random&#xff1a;生成…...

Spring 面试题【每日20道】【其二】

1、Spring MVC 具体的工作原理&#xff1f; 中等 Spring MVC 是 Spring 框架的一部分&#xff0c;专门用于构建基于Java的Web应用程序。它采用模型-视图-控制器&#xff08;MVC&#xff09;架构模式&#xff0c;有助于分离应用程序的不同方面&#xff0c;如输入逻辑、业务逻辑…...

嵌入式八股文面试题(一)C语言部分

1. 变量/函数的声明和定义的区别&#xff1f; &#xff08;1&#xff09;变量 定义不仅告知编译器变量的类型和名字&#xff0c;还会分配内存空间。 int x 10; // 定义并初始化x int x; //同样是定义 声明只是告诉编译器变量的名字和类型&#xff0c;但并不为它分配内存空间…...

Vue06

目录 一、声明式导航-导航链接 1.需求 2.解决方案 3.通过router-link自带的两个样式进行高亮 二、声明式导航的两个类名 1.router-link-active 2.router-link-exact-active 三、声明式导航-自定义类名&#xff08;了解&#xff09; 1.问题 2.解决方案 3.代码演示 四…...

deepseek-r1模型本地win10部署

转载自大佬&#xff1a;高效快速教你deepseek如何进行本地部署并且可视化对话 deepseek 如果安装遇到这个问题 Error: Post “http://127.0.0.1:11434/api/show”: read tcp 127. 用管理员cmd打开 接着再去切换盘符d: cd 文件夹 重新下载模型&#xff1a;ollama run deepseek…...

自定义数据集 使用scikit-learn中SVM的包实现SVM分类

生成自定义数据集 生成一个简单的二维数据集&#xff0c;包含两类数据点&#xff0c;分别用不同的标签表示。 import numpy as np import matplotlib.pyplot as plt# 生成数据 np.random.seed(42) X np.r_[np.random.randn(100, 2) - [2, 2], np.random.randn(100, 2) [2, …...

pandas的melt方法使用

Pandas 的 melt 方法用于将宽格式&#xff08;wide format&#xff09;的 DataFrame 转换为长格式&#xff08;long format&#xff09;的 DataFrame。这种转换在数据处理和可视化中非常有用&#xff0c;尤其是在处理多列数据时。 宽格式 vs 长格式 宽格式&#xff08;Wide F…...

一文讲解Spring中应用的设计模式

我们都知道Spring 框架中用了蛮多设计模式的&#xff1a; 工厂模式呢&#xff0c;就是用来创建对象的&#xff0c;把对象的创建和使用分开&#xff0c;这样代码更灵活。代理模式呢&#xff0c;是用一个代理对象来控制对真实对象的访问&#xff0c;可以在访问前后做一些处理。单…...

Linux的基本指令(下)

1.find指令 Linux下find命令在⽬录结构中搜索⽂件&#xff0c;并执⾏指定的操作。 Linux下find命令提供了相当多的查找条件&#xff0c;功能很强⼤。由于find具有强⼤的功能&#xff0c;所以它的选项也很多&#xff0c;其中⼤部分选项都值得我们花时间来了解⼀下。 即使系统中含…...

HAO的Graham学习笔记

前置知识&#xff1a;凸包 摘录oiwiki 在平面上能包含所有给定点的最小凸多边形叫做凸包。 其定义为&#xff1a;对于给定集合 X&#xff0c;所有包含 X 的凸集的交集 S 被称为 X 的 凸包。 说人话就是用一个橡皮筋包含住所有给定点的形态 如图&#xff1a; 正题&#xff1a…...

Elasticsearch Queries

Elasticsearch Compound Queries Elasticsearch 的 Compound Queries 是一种强大的工具&#xff0c;用于组合多个查询子句&#xff0c;以实现更复杂的搜索逻辑。这些查询子句可以是叶查询&#xff08;Leaf Queries&#xff09;或复合查询&#xff08;Compound Queries&#xf…...

利用matlab寻找矩阵中最大值及其位置

目录 一、问题描述1.1 max函数用法1.2 MATLAB中 : : :的作用1.3 ind2sub函数用法 二、实现方法2.1 方法一&#xff1a;max和find2.2 方法二&#xff1a;max和ind2sub2.3 方法对比 三、参考文献 一、问题描述 matlab中求最大值可使用函数max&#xff0c;对于一维向量&#xff0…...

SQL入门到精通 理论+实战 -- 在 MySQL 中学习SQL语言

目录 一、环境准备 1、MySQL 8.0 和 Navicat 下载安装 2、准备好的表和数据文件&#xff1a; 二、SQL语言简述 1、数据库基础概念 2、什么是SQL 3、SQL的分类 4、SQL通用语法 三、DDL&#xff08;Data Definition Language&#xff09;&#xff1a;数据定义语言 1、操…...

【智力测试——二分、前缀和、乘法逆元、组合计数】

题目 代码 #include <bits/stdc.h> using namespace std; using ll long long; const int mod 1e9 7; const int N 1e5 10; int r[N], c[N], f[2 * N]; int nr[N], nc[N], nn, nm; int cntr[N], cntc[N]; int n, m, t;void init(int n) {f[0] f[1] 1;for (int i …...

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

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

并发编程中的常见问题

1 竞态条件 (Race Condition) 定义:竞态条件是指多个线程在访问共享资源时,由于执行顺序的不同导致结果不确定的情况。 示例: public class Counter {private int count = 0;public void increment() {count++;}public int getCount() {return count;} }在多线程环境下,…...

二维前缀和:高效求解矩阵区域和问题

在处理二维矩阵时&#xff0c;频繁计算某一子矩阵的和是一个常见的操作。传统的做法是直接遍历该子矩阵&#xff0c;时间复杂度较高。当矩阵非常大且有大量的查询时&#xff0c;直接计算将变得低效。为了提高效率&#xff0c;我们可以通过 二维前缀和 技巧在常数时间内解决这个…...

鸢尾花书《编程不难》02---学习书本里面的三个案例

文章目录 1.引言2.第一个例子---模拟硬币的投掷结果3.第二个例子---混合两个一元高斯分布的随机数4.第三个例子---线性回归的作图5.关于书中的问题的解决方案 1.引言 今天的这个文章主要是阅读学习鸢尾花书系列的第一本《编程不难》&#xff0c;今天主要是记录下书里面的两个例…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...