type
Post
status
Published
date
Jun 3, 2024
slug
summary
tags
算法
二分查找
数组
category
算法
icon
password
给你一个按照非递减顺序排列的整数数组
nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target,返回 [-1, -1]。你必须设计并实现时间复杂度为
O(log n) 的算法解决此问题。示例 1:
示例 2:
示例 3:
提示:
0 <= nums.length <= 105
109 <= nums[i] <= 109
nums是一个非递减数组
109 <= target <= 109
思路:数组为有序数组,同时数组中无重复元素,一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当看到题目描述满足如上条件的时候,要想一想是不是可以用二分法了。
边界条件判定:当区间为[x,x]闭区间时,左可以等于右;当为开区间时,左≠右。
- Author:guderain
- URL:https://wangguanxi.space/article/1562b727-a3a3-80d7-b123-e598767afefe
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts

.webp?table=collection&id=92be88af-5f71-4631-9d3e-ee3bd53dcced&t=92be88af-5f71-4631-9d3e-ee3bd53dcced&width=1080&cache=v2)
