在排序数组中查找元素的第一个和最后一个位置
题目描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
题目解析
题目中要求了时间复杂度为O(log n),这就很清楚要使用二分查找法了。
首先定义两个指针变量，分别存储左右两个位置的索引。首先去找目标值的最左面的索引,通过循环为了防止元素丢失,每次保留最右面的元素,左侧的指针移动时+1。在循环结束的时候判断一下数组中是否包括目标值,不包括的话直接退出。 右面的跟左侧相同，只不过正好相反。
代码实现
相关推荐HOT
更多>>
xml解析器
SAX解析器：基于事件驱动的解析器，逐行读取XML文件并触发相应的事件，适用于处理大型XML文件，但需要手动编写事件处理器来处理XML文件中的数据...详情>>
2023-03-21 16:03:51
java全局变量
如果全局变量是一个对象，则可以更改该对象的状态，即使变量本身是final类型。当一个方法被调用时，会为该方法在栈上分配一块内存空间，用于存...详情>>
2023-03-17 10:01:40
带你手把手解决Java常见Bug
刚开始学习Java语言的小伙伴, 很可能被各种各样的程序bug搞得焦头烂额, 甚至被劝退。别怕，小编将手把手带你了解Java中的异常体系, 如何识别Bug...详情>>
2023-03-13 16:05:00
JavaScript 内的 this 指向
在 javascript 语言中, 有一个奇奇怪怪的 "关键字" 叫做 this详情>>
2023-03-07 15:21:00
京公网安备 11010802030320号