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

算法中二分搜索详解

文章目录

  • 在有序数组中找num是否存在
    • 实现思路
    • 实现代码(里面运用了对数器)
    • 在有序数组中找>=num的最左位置
    • 实现思路
    • 代码实现
  • 在有序数组中找<=num的最右位置
    • 实现思路
    • 实现代码
  • 二分搜索不一定发生在有序数组上(比如寻找峰值问题)
    • 题目描述
    • 实现思路
    • 实现代码

在有序数组中找num是否存在

实现思路

  1. 先定义左索引为0,有索引为数组长度-1
  2. 然后定义中间索引(在左索引和右索引的中间)
  3. 然后拿num和中间索引对应的数作比较,相等的话代表这个数存在。
  4. 如果num大于中间索引的数,因为是有序数组,中间索引左边的数都小于等于中间索引的数,所以要查找的数的范围是在中间索引右边到右索引里面,让其左索引等于中间索引加1,然后再从步骤2开始
  5. 如果要查找的数小于中间索引的数,那么应该在左索引到中间索引这个范围内,让右索引等于中间索引减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的最左位置

实现思路

  1. 先定义左索引为0,有索引为数组长度-1
  2. 然后定义中间索引(在左索引和右索引的中间)
  3. 定义最终一个索引为-1
  4. 判断中间索引的元素和num的比较情况
    1. num大,所以在中间索引右边的区域,重复步骤2
    2. num小,在左边的区域,让最终索引等于中间索引,看左边区域,重复步骤2
  5. 返回最终索引

代码实现

 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的最右位置

实现思路

  1. 和上面第二个的思路差不多。
  2. 用暴力解求索引时让其从后往前遍历,然后让其元素小于等于num
  3. 在通过最优解(二分查找)时,中间索引大于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. 先判断数组个数
    1. 如果个数为1,那么这个数就是峰值,返回0索引
    2. 如果不为1,也就是大于等于2
  2. 数组长度大于等于2
    1. 判断第一个数和第二个数的大小,如果第一个数大于第二个数,那么第一个数就是峰值
    2. 判断倒数第一个数和倒数第二个数,如果倒数第一个数大于倒数第二个数,那么倒数第一个数就是峰值
  3. 不属于步骤2的俩个条件,那么就可以用二分搜索
    1. 定义中间索引
    2. 判断中间索引数和中间索引数的前一个数,如果中间索引数小于中间索引数的前一个数,那么中间索引左边的范围必有峰值
    3. 判断中间索引数和中间索引数的后一个数,如果中间索引数小于中间索引数的后一个数,那么中间索引右边的范围必有峰值
    4. 如果上述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 推荐电路 讲解这个是官方推荐图 注意以下几点&#xff1a; NTC是100K的别买错了 L就是线圈 我这选用的A11 6.3 uH 淘宝买的 需要陪400nf NPO或CBB 还可以10uh配250nf&#xff08;这个我没试过&#xff09; 如果led2闪烁…...

[CSS]样式属性+元素设置

哎呀&#xff0c;好多东西&#xff0c;根本记不住&#xff0c;更多的还是边用边记吧&#xff0c;这里的代码就当使用范例&#xff0c;但其实如果可以让gpt应该会更好&#xff0c;哎学吧&#xff0c;反正记得住当然更好 文本 属性名描述word-break单词换行。取值如下&#xff1…...

优雅关闭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仿真程序设计报告原理图讲解视频&#xff09; 多功能洗衣机控制-强洗弱洗漂洗 1. 主要功能&#xff1a;2. 讲解视频&#xff1a;3. 仿真设计4. 程序代码5. 设计报告6. 原理图7. 设计资料内容清单资料下载链接&#xf…...

CVP(ChatGPT、Vector Database和Prompt)

CVP实际上指的是ChatGPT、Vector Database和Prompt的结合&#xff0c;这是一种新型的技术栈&#xff0c;用于构建智能应用。 首先&#xff0c;我们来看这三个组成部分&#xff1a; ChatGPT&#xff1a;这是一个强大的语言模型&#xff0c;它能够理解并生成自然语言文本。Chat…...

c语言-----数组知识汇总

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

【游戏开发之热更新技术】

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

小红的白色字符串

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

Python+Django+Html网页版人脸识别考勤打卡系统

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

第1章、react基础知识;

一、react学习前期准备&#xff1b; 1、基本概念&#xff1b; 前期的知识准备&#xff1a; 1.javascript、html、css&#xff1b; 2.构建工具&#xff1a;Webpack&#xff1a;https://yunp.top/init/p/v/1 3.安装node&#xff1a;npm&#xff1a;https://yunp.top/init/p/v/1 …...

物联网会用到哪些数据开发

物联网&#xff08;IoT&#xff09;涉及大量的设备和传感器&#xff0c;产生的数据种类繁多&#xff0c;因此在物联网领域进行数据开发时&#xff0c;可能涉及以下几个方面&#xff1a; 数据采集与存储&#xff1a; 设备数据采集&#xff1a;从各种传感器和设备中采集数据&…...

[Linux]一篇文章带你搞定软硬连接

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

AI常见关键术语

哈喽&#xff0c;大家好&#xff0c;我是小码哥&#xff0c;人工智能技术的快速发展带来了许多专业术语&#xff0c;这些词汇对于理解AI的工作原理和应用至关重要。以下是一些关键的AI术语&#xff0c;以及它们的专业解释和通俗总结。 一、核心概念 人工智能 (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鸿蒙端云一体化开发--适合小白体制

端云一体化 什么是“端”&#xff0c;什么是“云”&#xff1f; 答&#xff1a;“端“&#xff1a;手机APP端 “云”:后端服务端 什么是端云一体化&#xff1f; 端云一体化开发支持开发者在 DevEco Studio 内使用一种语言同时完成 HarmonyOS 应用的端侧与云侧开发。 …...

Quanto: PyTorch 量化工具包

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

宝塔面板Docker+Uwsgi+Nginx+SSL部署Django项目

这次为大家带来的是从零开始搭建一个django项目并将它部署到linux服务器上。大家可以按照我的步骤一步步操作&#xff0c;最终可以完成部署。 步骤1&#xff1a;在某个文件夹中创建一个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++

题目描述 某医院想统计一下某项疾病的获得与否与年龄是否有关&#xff0c;需要对以前的诊断记录进行整理&#xff0c;按照0-18岁、19-35岁、36-60岁、61以上&#xff08;含61&#xff09;四个年龄段统计的患病人数以及占总患病人数的比例。 输入 共2行&#xff0c;第一行为过…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

学校招生小程序源码介绍

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

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...