当前位置: 首页 > 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;/\…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...