mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-06 17:44:10 +08:00
37 lines
1.7 KiB
Markdown
Executable File
37 lines
1.7 KiB
Markdown
Executable File
# [34. Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)
|
||
|
||
|
||
## 题目
|
||
|
||
Given an array of integers `nums` sorted in ascending order, find the starting and ending position of a given `target` value.
|
||
|
||
Your algorithm's runtime complexity must be in the order of *O*(log *n*).
|
||
|
||
If the target is not found in the array, return `[-1, -1]`.
|
||
|
||
**Example 1:**
|
||
|
||
Input: nums = [5,7,7,8,8,10], target = 8
|
||
Output: [3,4]
|
||
|
||
**Example 2:**
|
||
|
||
Input: nums = [5,7,7,8,8,10], target = 6
|
||
Output: [-1,-1]
|
||
|
||
## 题目大意
|
||
|
||
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。
|
||
|
||
|
||
## 解题思路
|
||
|
||
- 给出一个有序数组 `nums` 和一个数 `target`，要求在数组中找到第一个和这个元素相等的元素下标，最后一个和这个元素相等的元素下标。
|
||
- 这一题是经典的二分搜索变种题。二分搜索有 4 大基础变种题：
|
||
1. 查找第一个值等于给定值的元素
|
||
2. 查找最后一个值等于给定值的元素
|
||
3. 查找第一个大于等于给定值的元素
|
||
4. 查找最后一个小于等于给定值的元素
|
||
|
||
这一题的解题思路可以分别利用变种 1 和变种 2 的解法就可以做出此题。或者用一次变种 1 的方法，然后循环往后找到最后一个与给定值相等的元素。不过后者这种方法可能会使时间复杂度下降到 O(n)，因为有可能数组中 n 个元素都和给定元素相同。(4 大基础变种的实现见代码)
|