本次刷题日记的第 72 篇，力扣题为：34. 在排序数组中查找元素的第一个和最后一个位置，中等
一、题目描述：
今天回来加点紧，写一个随机中等题练练手，34. 在排序数组中查找元素的第一个和最后一个位置，看看需要我们咋找
二、这道题考察了什么思想？你的思路是什么？
- 在排序数组中查找元素的第一个和最后一个位置 给了我们哪些有用的信息：
- 题目给出一个数组，是有序的，且是升序的，元素是整型的数字，题目给出一个 target ，要求我们找到 target 对应到数组中的开始位置和结束位置，这里指的是数组索引的位置
- 题目要求我们时间复杂度是 O(nlogn)
- 当然，题目给出的数组中，并不一定存在给出的 target 值，如果不存在，则返回 [-1,-1]
分析
其实看到这道题，有一点我们就能够非常明确了，那就是题目给出的数组是升序的，另外题目要求我们做的一件事情是去做查找
稍加一想，我们就应该要考虑，这个题是不是要用 二分法来进行处理，是否合适
其实我们拿到题，最无脑的就是遍历一遍数组，记录下 target 出现的第一个位置和最后一个位置，输出结果即可，但是，题目有时间复杂度的要求，咱不能这么干
那么二分法使用啥情况呢？
- 适用于对于有序的一串数字中高效的查找某一个数字
那么应对到咱们这个题可以知道，我们是要找 1 个数字的最开始位置和最尾巴位置，那么找第一个数字的时候从头开始找？最后一个位置的时候，从尾巴开始找？说起来咋有点像是双指针
不过我们可以这样来做，同样是无脑的使用二分法做查找，思考一下，我们是不是可以从左到右找 target ，找到 target 就是第一个位置
那么 target 的最后一个位置，我们可以是找比 target 大的数字就可以了，找到之后，索引减去 1 ，就是 target 的最后一个位置了
那么对应到 golang 中，我们可以使用一下库函数，库函数用起来总比咱们的手撸代码效率高吧
咱们可以使用 golang 中 sort 库的 SearchInts 函数
SearchInts 在排序的整数切片中搜索 x 并返回 Search 指定的索引。， 如果 x 不存在，则返回值是插入 x 的索引
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
- 我们可以自己写二分，也可以使用库函数，不过我们可以感受一个库函数带给我们的高效，兄弟们可以尝试一下自己写二分法，和使用库做出的题，效率分别都是咋样的
编码如下：
func searchRange(nums []int, target int) []int { left := sort.SearchInts(nums, target) if left == len(nums) || nums[left] != target { return []int{-1, -1} } right := sort.SearchInts(nums, target + 1) - 1 return []int{left, right} }
四、总结：
时间复杂度没的说，题目就是要求我们时间复杂度保持 O(nlogn)
空间复杂度这里比较明确，我们就引入了一些常数级别的变量，因此空间复杂度为 O(1)
原题地址：34. 在排序数组中查找元素的第一个和最后一个位置
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
