LeetCode—704. 二分查找(简单)

devtools/2024/11/26 16:20:10/

仅供个人学习使用

题目描述:

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1

示例 1:

输入: nums= [-1,0,3,5,9,12], target= 9
输出: 4
解释: 9 出现在nums中并且下标为 4

示例 2:

输入: nums= [-1,0,3,5,9,12], target= 2
输出: -1
解释: 2 不存在nums中因此返回 -1

 题目解析:

本题的实质是二分查找,定义左右两个指针left、right,开始时分别指向数组的首和尾,以及一个中间值mid=(left+right)/2。然后就是分情况讨论,mid和target的大小关系:

  • nums[mid]=target,直接返回mid;
  • nums[mid]<target,则说明target在mid的右边,left指针移动到mid的右边,即left=mid+1;
  • nums[mid]>target,则说明target在mid的左边,right指针移动到mid的左边,即right=mid-1;

实现代码:

class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length-1;while(left<=right){int mid = (left+right)/2;if(nums[mid] == target){return mid;}else if(nums[mid]>target){right = mid-1;}else{left = mid+1;}}return -1;  //查找失败}
}


http://www.ppmy.cn/devtools/137162.html

相关文章

《硬件架构的艺术》笔记(五):低功耗设计

介绍 能量以热量形式消耗&#xff0c;温度升高芯片失效率也会增加&#xff0c;增加散热片或风扇会增加整体重量和成本&#xff0c;在SoC级别对功耗进行控制就可以减少甚至可能消除掉这些开支&#xff0c;产品也更小更便宜更可靠。本章描述了减少动态功耗和静态功耗的各种技术。…

一场开源视角的AI会议即将在南京举办

一场开源视角的AI会议&#xff0c;将于2024年11月30日在南京举办。 此次活动&#xff0c;知名开源导师-庄表伟老师将为大家介绍自己搭建的AI框架&#xff0c;同时被誉为2024年度的“开源之星”、[开源之道]主创适兕老师也将亲临南京为大家分享AI话题。 与此同时&#xff0c;您还…

uni-app 界面TabBar中间大图标设置的两种方法

一、前言 最近写基于uni-app 写app项目的时候&#xff0c;底部导航栏 中间有一个固定的大图标&#xff0c;并且没有激活状态。这里记录下实现方案。效果如下&#xff08;党组织这个图标&#xff09;&#xff1a; 方法一&#xff1a;midButton的使用 官方文档&#xff1a;ta…

机器学习-----变色龙算法(Chameleon Algorithm)

变色龙算法&#xff08;Chameleon Algorithm&#xff09; 简介 变色龙算法是一种基于图论的聚类算法&#xff0c;它通过结合数据点间的相似性和簇内的紧密性&#xff0c;适应不同数据集的特点&#xff0c;从而进行灵活的聚类。变色龙算法的关键步骤包括&#xff1a; K近邻图…

大模型(LLMs)推理篇

大模型&#xff08;LLMs&#xff09;推理篇 1. 为什么大模型推理时显存涨的那么多还一直占着&#xff1f; 首先&#xff0c;序列太长了&#xff0c;有很多Q/K/V&#xff1b;其次&#xff0c;因为是逐个预测next token&#xff0c;每次要缓存K/V加速解码。 大模型在gpu和cpu上…

小R的随机播放顺序

问题描述 小R有一个特殊的随机播放规则。他首先播放歌单中的第一首歌&#xff0c;播放后将其从歌单中移除。如果歌单中还有歌曲&#xff0c;则会将当前第一首歌移到最后一首。这个过程会一直重复&#xff0c;直到歌单中没有任何歌曲。 例如&#xff0c;给定歌单 [5, 3, 2, 1,…

一台电脑最多支持几个分区

MBR分区表 如果硬盘使用MBR&#xff08;主引导记录&#xff09;分区表&#xff0c;最多可以支持4个主分区&#xff0c;或者3个主分区加上一个扩展分区。扩展分区内可以创建多个逻辑分区&#xff0c;但逻辑分区的数量没有限制。因此&#xff0c;在MBR分区表下&#xff0c;最多可…

代谢组数据分析(二十二):Zscore标准化后主成分分析(PCA)及热图展示

禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍Z-score标准化主成分分析(Principal Component Analysis,PCA)加载R包数据下载导入数据数据预处理填补缺失值Zscore标准化PCA分析热图展示代谢物聚类簇小提琴图聚类分析总结系统信…