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

[utterances-bot]

0034. 在排序数组中查找元素的第一个和最后一个位置 | 算法通关手册

34. 在排序数组中查找元素的第一个和最后一个位置 # 标签：数组、二分查找 难度：中等 题目大意 # 给定一个升序数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。要求使用时间复杂度为 $O(log n)$ 的算法解决问题。
    解题思路 # 要求使用时间复杂度为 $O(logn)$ 的算法解决问题，那么就需要使用「二分查找算法」了。这道题明显就是对「二分查找」的考察。
    进行两次二分查找，第一次尽量向左搜索。第二次尽量向右搜索。
    代码 # 1 2 3 4

https://algo.itcharge.cn/Solutions/0001-0099/find-first-and-last-position-of-element-in-sorted-array

[RunKeepRuning]

为什么第一次尽量要向左，第二次要尽量向右呢？

[RunKeepRuning]

最后一句的if nums[left] == target是否还有用呢? 上面不是判断过是否存在该元素了吗？ 去掉这个if也通过了所有测例，想请问下这个最后if的作用感谢楼主

[itcharge]

为什么第一次尽量要向左，第二次要尽量向右呢？

这是因为数组中可能会有值等于 target 的重复元素，比如与在数组 [1, 2, 3, 3, 3, 3, 5, 6] 中查找元素 3 的第一个和最后一个位置。第一次尽量向左是为了查找元素 3 在数组中最左边的位置，第二次尽量向右是为了查找元素 3 在数组中最右边的位置。

[itcharge]

最后一句的if nums[left] == target是否还有用呢? 上面不是判断过是否存在该元素了吗？ 去掉这个if也通过了所有测例，想请问下这个最后if的作用感谢楼主

有用的，while 循环中的条件是 left < right，跳出 while 循环的条件是 left == right，但是这时候会出现两种情况。第一种是数组中包含 target 元素，此时 nums[left] == target。第二种情况是数组中不包含 target 元素，此时 nums[left] != target。这里针对第二种特殊情况就需要判断一下 nums[left] 是否等于 target。