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

【算法】二分法

1、二分法

1.1 二分法原理

        每次将查找的范围缩小一半,直到最后找到记录或者找不到记录返回。

        要求:采用二分法查找时,数据需是排好序的。

1.2二分法思路

        判断某个数是否在数组中存在(例:判断3是否在数组中存在)

       (1)对于排好序的数组,进行第一轮分半,找到第4个位置

        (2) 3比4小,因此向左边查找,进行第二轮分半,找到第2个位置

        (3)3比2大,因此向右边查找,进行第三轮分半,但只有1个位置了,因此直接判断数据是否是3,结束查找。

2、算法分析

2.1逻辑分析

        由于其对半分的规则,如果所需要的结果刚好在中间位置,则一次获取结果

        如果其

2.2 时间复杂度

        由于其操作方法为,每次对半处理,其时间复杂度为

3、code

3.1 java

public static boolean exist(int[] arr, int target) {if(arr == null || arr.length == 0){return false;}int left = 0;int right = arr.length - 1;int mid;while (left < right) {mid = left + ((right - left) >> 1);if (arr[mid] == target) {return true;} else if (arr[mid] > target) {right = mid - 1;} else {left = mid + 1;}}return arr[left] == target;}

3.2 python

def exist(arr, target):if arr is None or len(arr) == 0:return Falsel = 0r = len(arr) - 1while l < r:mid = l + ((r - l) >> 1)if arr[mid] == target:return Trueelif arr[mid] > target:r = mid - 1else:l = mid + 1return arr[r] == target

相关文章:

【算法】二分法

1、二分法 1.1 二分法原理 每次将查找的范围缩小一半&#xff0c;直到最后找到记录或者找不到记录返回。 要求&#xff1a;采用二分法查找时&#xff0c;数据需是排好序的。 1.2二分法思路 判断某个数是否在数组中存在&#xff08;例&#xff1a;判断3是否在数组中存在&#…...

2023.12.18 JAVA学习day03,while与for循环

目录 0.switch 判断语句 一.for循环 1.简单练习 2.使用for循环计算1-100求和, 以及偶数求和 3.进阶练习,配合键盘录入与判断使用循环 二.while循环 三种格式的区别&#xff1a; 0.switch 判断语句 switch (表达式) { case 1: 语句体1; break; case …...

使用Pytorch从零开始构建StyleGAN2

这篇博文是关于 StyleGAN2 的&#xff0c;来自论文Analyzing and Improving the Image Quality of StyleGAN&#xff0c;我们将使用 PyTorch 对其进行干净、简单且可读的实现&#xff0c;并尝试尽可能地还原原始论文。 如果您没有阅读 StyleGAN2 论文。或者不知道它是如何工作…...

C++ Qt 开发:ListWidget列表框组件

Qt 是一个跨平台C图形界面开发库&#xff0c;利用Qt可以快速开发跨平台窗体应用程序&#xff0c;在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置&#xff0c;实现图形化开发极大的方便了开发效率&#xff0c;本章将重点介绍ListWidget列表框组件的常用方法及灵活运用。…...

手机天线市场分析:预计2029年将达到576亿美元

手机天线&#xff0c;即手机上用于接收信号的设备&#xff0c;旧式手机有外凸式天线&#xff0c;新式手机多数已隐藏在机身内。这类天线主要都在手机内部&#xff0c;手机外观上看不到里面的东西。 手机天线主要就内置及外置天线两种&#xff0c;内置天线客观上必然比外置天线弱…...

FPGA引脚分配的问题

今天在做一个FPGA的实验时&#xff0c;在引脚分配时失败了&#xff0c;出现了如下报错&#xff1a; 我当时分配的引脚是PIN_AE19&#xff0c;然而奇怪的是我之前并未分配这个引脚&#xff0c;我使用的开发工具是Quartus II 9.1 Web Edition&#xff0c;算个老版本了。 有的网站…...

面试经典150题(27-28)

leetcode 150道题 计划花两个月时候刷完&#xff0c;今天&#xff08;第十三天&#xff09;完成了2道(27-28)150&#xff1a; 今天这两道是真的汗流浃背&#xff01;&#xff01;&#xff01; 27.&#xff08;209. 长度最小的子数组&#xff09;题目描述&#xff1a; 给定一…...

计算机图形学头歌合集(题集附解)

目录 CG1-v1.0-点和直线的绘制 第1关&#xff1a;OpenGL点的绘制 第2关&#xff1a;OpenGL简单图形绘制 第3关&#xff1a;OpenGL直线绘制 第4关&#xff1a;0<1直线绘制-dda算法<> 第5关&#xff1a;0<1直线绘制-中点算法<> 第6关&#xff1a;一般直线绘…...

MacBook Air提供了丰富多彩的截图选项,大到整个屏幕,小到具体的区域

本指南将带你了解在MacBook Air笔记本电脑上进行屏幕截图的各种方法。它涵盖了所有用于截屏的键盘快捷键,还包括如何启动MacBook Air屏幕录制和更改屏幕截图设置的信息。 如何在MacBook Air上进行屏幕截图 在MacBook上进行整个屏幕截图的最快、最简单的方法是使用command+sh…...

【CMU 15-445】Lecture 12: Query Execution I 学习笔记

Query Execution I Processing ModelsIterator ModelMaterialization ModelVectorization Model Access MethodsSequential ScanIndex Scan Modification QueriesHalloween Problem 本节课主要介绍SQL语句执行的相关机制。 Processing Models 首先是处理模型&#xff0c;它定义…...

低代码开发平台的优势及应用场景分析

文章目录 低代码是什么&#xff1f;低代码起源低代码分类低代码的能力低代码的需求市场需要专业开发者需要数字化转型需要 低代码的趋势如何快速入门低代码开发低代码应用领域 低代码是什么&#xff1f; 低代码&#xff08;Low-code&#xff09;是著名研究机构Forrester于2014…...

ES常见查询总结

目录 1:查询总数2:查询所有数据3:查询指定条数4:根据ID查询5:一个查询字符串搜索6:match搜索7:term搜索8:bool搜索9:must多条件匹配查询10:Should满足一个条件查询11: must_not必须不匹配查询12:多个字段查询内容13:一个字段查询多个内容14:通配符和正则匹配15:前缀查询16:短语…...

Spring Boot Docker Compose 支持中文文档

本文为官方文档直译版本。原文链接 Spring Boot Docker Compose 支持中文文档 引言服务连接自定义镜像跳过特定的容器使用特定Compose文件等待容器就绪控制 Docker Compose 的生命周期激活 Docker Compose 配置文件 引言 Docker Compose 是一种流行的技术&#xff0c;可用于为…...

智慧城市/一网统管建设:人员危险行为检测算法,为城市安全保驾护航

随着人们压力的不断增加&#xff0c;经常会看见在日常生活中由于小摩擦造成的大事故。如何在事故发生时进行及时告警&#xff0c;又如何在事故发生后进行证据搜索与事件溯源&#xff1f;旭帆科技智能视频监控人员危险行为/事件检测算法可以给出答案。 全程监控&#xff0c;有源…...

C语言:求和1+1/2-1/3+1/4-1/5+……-1/99+1/100

#include<stdio.h> int main() {int i 0;double sum 0.0;int flag 1;for (i 1;i < 100;i){sum 1.0 / i * flag;flag -flag;}printf("sum%lf\n", sum);return 0; }...

学习什么知识不会过时

近况&#x1f481;&#x1f3fb; 最近这段时间&#xff0c;我真的很糟糕。工作中满负荷做需求&#xff0c;闲了就想玩游戏放松&#xff0c;业余搞些东西的时间很少。本来就有些焦虑&#xff0c;这种状态下更是有些 suffering。究其原因&#xff0c;都是因为部门转换的问题。 一…...

C# WPF上位机开发(ExtendedWPFToolkit扩展包使用)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 虽然个人人为当前的c# wpf内容已经足够多&#xff0c;但是肯定还是有很多个性化的需求没有满足。比如说不够好看&#xff0c;比如说动画效果不好&a…...

【IOS开发】传感器 SensorKit

资源 官方文档 https://developer.apple.com/search/?qmotion%20graph&typeDocumentation SensorKit 使应用程序能够访问选定的原始数据或系统从传感器处理的指标。 步骤信息加速度计或旋转速率数据用户手腕上手表的配置物理环境中的环境光有关用户日常通勤或旅行的详细…...

【C++】封装:练习案例-点和圆的关系

练习案例&#xff1a;点和圆的关系 设计一个圆形类&#xff08;Circle&#xff09;&#xff0c;和一个点类&#xff08;Point&#xff09;&#xff0c;计算点和圆的关系。 思路&#xff1a; 1&#xff09;创建点类point.h和point.cpp 2&#xff09;创建圆类circle.h和circle…...

【vue】正则表达式限制input的输入:

文章目录 1、只能输入大小写字母、数字、下划线&#xff1a;/[^\w_]/g2、只能输入小写字母、数字、下划线&#xff1a;/[^a-z0-9_]/g3、只能输入数字和点&#xff1a;/[^\d.]/g4、只能输入小写字母、数字、下划线&#xff1a;/[^\u4e00-\u9fa5]/g5、只能输入数字&#xff1a;/\…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...