算法中二分搜索详解
文章目录
- 在有序数组中找num是否存在
- 实现思路
- 实现代码(里面运用了对数器)
- 在有序数组中找>=num的最左位置
- 实现思路
- 代码实现
- 在有序数组中找<=num的最右位置
- 实现思路
- 实现代码
- 二分搜索不一定发生在有序数组上(比如寻找峰值问题)
- 题目描述
- 实现思路
- 实现代码
在有序数组中找num是否存在
实现思路
- 先定义左索引为0,有索引为数组长度-1
- 然后定义中间索引(在左索引和右索引的中间)
- 然后拿num和中间索引对应的数作比较,相等的话代表这个数存在。
- 如果num大于中间索引的数,因为是有序数组,中间索引左边的数都小于等于中间索引的数,所以要查找的数的范围是在中间索引右边到右索引里面,让其左索引等于中间索引加1,然后再从步骤2开始
- 如果要查找的数小于中间索引的数,那么应该在左索引到中间索引这个范围内,让右索引等于中间索引减1,再从步骤2开始
实现代码(里面运用了对数器)
public static void main(String[] args) {int N = 100;int V = 1000;int testTime = 500000;System.out.println("测试开始");for (int i = 0; i < testTime; i++) {//[0,1) * 100 <=> [0,100)int n = (int) (Math.random() * N);int[] arr = randomArray(n, V);Arrays.sort(arr);int num = (int) (Math.random() * V);int a = right(arr,num);int b = getIndex(arr,num);if (a != b){System.out.println("出错了!");}}System.out.println("测试结束");}public static int right(int[] arr, int num) {if (Arrays.binarySearch(arr, num) >= 0){return Arrays.binarySearch(arr, num) ;}else {return -1;}}public static int getIndex(int[] arr, int num) {if (arr == null || arr.length == 0) {return -1;}int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == num) {return mid;} else if (arr[mid] > num) {right = mid - 1;} else {left = mid + 1;}}return -1;}public static int[] randomArray(int n, int v) {int[] arr = new int[n];for (int i = 0; i < n; i++) {//[0,1) * 1000 + 1 <=> [1,1000]arr[i] = (int) (Math.random() * v) + 1;}return arr;}
在有序数组中找>=num的最左位置
实现思路
- 先定义左索引为0,有索引为数组长度-1
- 然后定义中间索引(在左索引和右索引的中间)
- 定义最终一个索引为-1
- 判断中间索引的元素和num的比较情况
- num大,所以在中间索引右边的区域,重复步骤2
- num小,在左边的区域,让最终索引等于中间索引,看左边区域,重复步骤2
- 返回最终索引
代码实现
public static void main(String[] args) {int N = 100;int V = 1000;int testTime = 500000;System.out.println("测试开始");for (int i = 0; i < testTime; i++) {int n = (int) (Math.random() * N);int[] arr = randomArray(n, V);Arrays.sort(arr);int num = (int) Math.random() * V;if (rightIndex(arr,num) != getIndex(arr,num)){System.out.println("出错了!");}}System.out.println("测试结束");}public static int[] randomArray(int n, int v) {int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = (int) (Math.random() * v + 1);}return arr;}public static int rightIndex(int[] arr, int num) {for (int i = 0; i < arr.length; i++) {if (arr[i] >= num) {return i;}}return -1;}public static int getIndex(int[] arr, int num) {int left = 0;int right = arr.length - 1;int ans = -1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] < num){left = mid + 1;}else {ans = mid;right = mid -1;}}return ans;}
在有序数组中找<=num的最右位置
实现思路
- 和上面第二个的思路差不多。
- 用暴力解求索引时让其从后往前遍历,然后让其元素小于等于num
- 在通过最优解(二分查找)时,中间索引大于num时,范围就编程中间索引的左边;反之最终索引等于中间索引,然后范围在中间索引的右边
实现代码
public static void main(String[] args) {int N = 100;int V = 1000;int testTime = 500000;System.out.println("测试开始");for (int i = 0; i < testTime; i++) {int n = (int) (Math.random() * N);int[] arr = randomArray(n, V);Arrays.sort(arr);int num = (int) Math.random() * V;if (rightIndex(arr,num) != getIndex(arr,num)){System.out.println("出错了!");}}System.out.println("测试结束");}public static int[] randomArray(int n, int v) {int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = (int) (Math.random() * v + 1);}return arr;}public static int rightIndex(int[] arr, int num) {for (int i = arr.length - 1; i >= 0; i--) {if (arr[i] <= num) {return i;}}return -1;}public static int getIndex(int[] arr, int num) {int left = 0;int right = arr.length - 1;int ans = -1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] > num){right = mid - 1;}else {ans = mid;left = mid + 1;}}return ans;}
二分搜索不一定发生在有序数组上(比如寻找峰值问题)
题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 arr,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。
你可以假设 arr[-1] = arr[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
实现思路
- 先判断数组个数
- 如果个数为1,那么这个数就是峰值,返回0索引
- 如果不为1,也就是大于等于2
- 数组长度大于等于2
- 判断第一个数和第二个数的大小,如果第一个数大于第二个数,那么第一个数就是峰值
- 判断倒数第一个数和倒数第二个数,如果倒数第一个数大于倒数第二个数,那么倒数第一个数就是峰值
- 不属于步骤2的俩个条件,那么就可以用二分搜索
- 定义中间索引
- 判断中间索引数和中间索引数的前一个数,如果中间索引数小于中间索引数的前一个数,那么中间索引左边的范围必有峰值
- 判断中间索引数和中间索引数的后一个数,如果中间索引数小于中间索引数的后一个数,那么中间索引右边的范围必有峰值
- 如果上述bc都不成立,那么中间索引数为峰值
实现代码
public int findPeakPoint(int[] arr) {int n = arr.length;if (arr == null || arr.length == 0) {return -1;}if (arr.length == 1) {return 0;}if (arr[0] > arr[1]) {return 0;}if (arr[n - 1] > arr[n - 2]) {return n - 1;}int left = 1;int right = n - 2;int ans = -1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid - 1] > arr[mid]) {right = mid - 1;} else if (arr[mid] < arr[mid + 1]) {left = mid + 1;} else {ans = mid;break;}}return ans;}
相关文章:
算法中二分搜索详解
文章目录 在有序数组中找num是否存在实现思路实现代码(里面运用了对数器)在有序数组中找>num的最左位置实现思路代码实现 在有序数组中找<num的最右位置实现思路实现代码 二分搜索不一定发生在有序数组上(比如寻找峰值问题)题目描述实现思路实现代码 在有序数组中找num是…...

关于无线充电项目总结IP6826
1、电路 1.1 选用芯片IP6826英集芯 支持PD3.0 5-15W 1.2 推荐电路 讲解这个是官方推荐图 注意以下几点: NTC是100K的别买错了 L就是线圈 我这选用的A11 6.3 uH 淘宝买的 需要陪400nf NPO或CBB 还可以10uh配250nf(这个我没试过) 如果led2闪烁…...

[CSS]样式属性+元素设置
哎呀,好多东西,根本记不住,更多的还是边用边记吧,这里的代码就当使用范例,但其实如果可以让gpt应该会更好,哎学吧,反正记得住当然更好 文本 属性名描述word-break单词换行。取值如下࿱…...
优雅关闭jar程序shell 脚本
参考竽道Linux部署 #!/bin/bash set -eDATE$(date %Y%m%d%H%M) # 基础路径 BASE_PATH/work/projects/yudao-server # 服务名称。同时约定部署服务的 jar 包名字也为它。 SERVER_NAMEyudao-server # 环境 PROFILES_ACTIVEdev# heapError 存放路径 HEAP_ERROR_PATH$BASE_PATH/he…...

基于51单片机多功能洗衣机控制(强洗弱洗漂洗)设计( proteus仿真+程序+设计报告+原理图+讲解视频)
基于51单片机多功能洗衣机控制(强洗弱洗漂洗)设计( proteus仿真程序设计报告原理图讲解视频) 多功能洗衣机控制-强洗弱洗漂洗 1. 主要功能:2. 讲解视频:3. 仿真设计4. 程序代码5. 设计报告6. 原理图7. 设计资料内容清单资料下载链接…...
CVP(ChatGPT、Vector Database和Prompt)
CVP实际上指的是ChatGPT、Vector Database和Prompt的结合,这是一种新型的技术栈,用于构建智能应用。 首先,我们来看这三个组成部分: ChatGPT:这是一个强大的语言模型,它能够理解并生成自然语言文本。Chat…...

c语言-----数组知识汇总
前言 本文为我学习数组知识点之后,对c语言的数组部分进行的知识点汇总。 简单数组介绍 简单来说,数组就是一个数据组,像一个箱子,里面放有多个数据。 [1,2,3,4,5] 数组的定义 基础定义 语法: 数据类型 数组名[数组…...

【游戏开发之热更新技术】
游戏开发之热更新技术 热更新技术是指在不重新发布和安装应用的情况下,对已部署的应用程序进行更新和修补的技术。这种技术在现代软件开发中变得越来越重要,因为它能够为用户提供更加及时的服务和更好的体验。以下是一篇关于热更新技术的文章࿰…...

小红的白色字符串
题目描述 小红拿到了一个字符串,她准备将一些字母变成白色,变成白色的字母看上去就和空格一样,这样字符串就变成了一些单词。 现在小红希望,每个单词都满足以下两种情况中的一种: 1.开头第一个大写,其余为…...

Python+Django+Html网页版人脸识别考勤打卡系统
程序示例精选 PythonDjangoHtml人脸识别考勤打卡系统 如需安装运行环境或远程调试,见文章底部个人QQ名片,由专业技术人员远程协助! 前言 这篇博客针对《PythonDjangoHtml网页版人脸识别考勤打卡系统》编写代码,代码整洁…...

第1章、react基础知识;
一、react学习前期准备; 1、基本概念; 前期的知识准备: 1.javascript、html、css; 2.构建工具:Webpack:https://yunp.top/init/p/v/1 3.安装node:npm:https://yunp.top/init/p/v/1 …...
物联网会用到哪些数据开发
物联网(IoT)涉及大量的设备和传感器,产生的数据种类繁多,因此在物联网领域进行数据开发时,可能涉及以下几个方面: 数据采集与存储: 设备数据采集:从各种传感器和设备中采集数据&…...

[Linux]一篇文章带你搞定软硬连接
阅读导览: 先在windows中先见见软硬连接从名字、inode等方面分析软硬连接如何实现软硬连接硬链接注意事项软硬链接都用来干什么如何在windows中实现硬链接 文章目录 概念简述文件系统windows下的快捷方式--软硬链接的直观体现角度1:文件名角度2ÿ…...

AI常见关键术语
哈喽,大家好,我是小码哥,人工智能技术的快速发展带来了许多专业术语,这些词汇对于理解AI的工作原理和应用至关重要。以下是一些关键的AI术语,以及它们的专业解释和通俗总结。 一、核心概念 人工智能 (AI) 专业解释&am…...

DataX案例,MongoDB数据导入HDFS与MySQL
【尚硅谷】Alibaba开源数据同步工具DataX技术教程_哔哩哔哩_bilibili 目录 1、MongoDB 1.1、MongoDB介绍 1.2、MongoDB基本概念解析 1.3、MongoDB中的数据存储结构 1.4、MongoDB启动服务 1.5、MongoDB小案例 2、DataX导入导出案例 2.1、读取MongoDB的数据导入到HDFS 2…...

HarmonyOS鸿蒙端云一体化开发--适合小白体制
端云一体化 什么是“端”,什么是“云”? 答:“端“:手机APP端 “云”:后端服务端 什么是端云一体化? 端云一体化开发支持开发者在 DevEco Studio 内使用一种语言同时完成 HarmonyOS 应用的端侧与云侧开发。 …...

Quanto: PyTorch 量化工具包
量化技术通过用低精度数据类型 (如 8 位整型 (int8)) 来表示深度学习模型的权重和激活,以减少传统深度学习模型使用 32 位浮点 (float32) 表示权重和激活所带来的计算和内存开销。 减少位宽意味着模型的内存占用更低,这对在消费设备上部署大语言模型至关…...

宝塔面板Docker+Uwsgi+Nginx+SSL部署Django项目
这次为大家带来的是从零开始搭建一个django项目并将它部署到linux服务器上。大家可以按照我的步骤一步步操作,最终可以完成部署。 步骤1:在某个文件夹中创建一个django项目 安装django pip install django创建一个django项目将其命名为djangoProject …...
Android 无线调试 adb connect ip:port 失败
1. 在手机打开 无线调试 使用 adb connect 连接 adb connect 192.168.14.164:39511如果连接成功, 查看连接的设备, 忽略 配对下面的步骤. adb devices如果连接失败: failed to connect to 192.168.14.164:39511如果失败了, 可以杀死一下进程, 然后执行后面的操作 adb kill…...

年龄与疾病c++
题目描述 某医院想统计一下某项疾病的获得与否与年龄是否有关,需要对以前的诊断记录进行整理,按照0-18岁、19-35岁、36-60岁、61以上(含61)四个年龄段统计的患病人数以及占总患病人数的比例。 输入 共2行,第一行为过…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...