LeetCode题解：在排序数组中查找元素的第一个和最后一个位置

冷不防 2022-12-28 14:14 56阅读 0赞

# 在排序数组中查找元素的第一个和最后一个位置（middle） #

## 一、题目 ##

[LeetCode 34.在排序数组中查找元素的第一个和最后一个位置][LeetCode 34.]

给定一个按照升序排列的整数数组 `nums`，和一个目标值 `target`。找出给定目标值在数组中的开始位置和结束位置，如果数组中不存在目标值 target，返回 \[-1, -1\]。

你可以设计并实现时间复杂度为 `O(log n)` 的算法解决此问题吗？

**示例 1：**

输入：nums = [5,7,7,8,8,10], target = 6
    输出：[-1,-1]

**示例 2：**

输入：nums = [5,7,7,8,8,10], target = 8
    输出：[3,4]

**提示：**

*  nums 是一个非递减数组

## 二、基础模版 III ##

因为我们的判断区间最少为2个元素，所以我们要注意循环的执行条件

1.  简单的判断边界： `nums.length === 0，return -1`；
2.  定义初始的左右边界：`left = 0, right = nums.length - 1`；
3.  确定执行条件：`left + 1 < right`，这也意味着查找区间要存在 3 个元素；
4.  向左查找时：`right = mid`；
5.  向左查找时：`left = mid`；
6.  判断剩下的两个元素哪个符合目标元素，并返回结果；

## 三、题解 ##

**分析模版**

*  我们的目标是：寻找目标值的起始下标和终止下标，但它是可能重复的
 *  针对这样的情况，我们要将判断拆解成查找目标首次出现的位置，和最后一次出现的位置\\
 *  我们讲一个大问题，用拆分成2个小问题，并用二分但解决对应的问题

## 四、写在最后 ##

本文是`二分查找-模版III` 的第一题，后面的几道题的也算是本模版的微调版，加油～

如果对你有所帮助不妨给本项目的[github 点个 star][github _ star]，这是对我最大的鼓励

**关于我**

*  花名：余光
 *  WX：j565017805
 *  沉迷 JS，水平有限，虚心学习中

**其他沉淀**

*  [JavaScript 版 LeetCode 题解][JavaScript _ LeetCode]
 *  [前端进阶笔记][Link 1]
 *  [CSDN][]

![yuguang-csdn-bottom.gif][]

\`\`\`\`

[LeetCode 34.]: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[github _ star]: https://github.com/webbj97/summary
[JavaScript _ LeetCode]: https://webbj97.github.io/leetCode-Js/
[Link 1]: https://webbj97.github.io/summary/
[CSDN]: https://yuguang.blog.csdn.net/
[yuguang-csdn-bottom.gif]: /images/20221120/3092266402d546f29156454c5f4b95be.png