在排序数组中查找元素的第一个和最后一个位置
力扣链接：34. 在排序数组中查找元素的第一个和最后一个位置
题目描述：
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
1.1 算法思路——二分查找
使用的还是二分思想，就是根据数据的性质，在某种判断条件下将区间一分为二，然后舍去其中一个区间，然后在另一个区间内查找。方便叙述，用 x 表示该元素，resLeft 表示左边界，resRight 表示右边界。
1.2 后两个模版：思路
1.2.1 寻找左边界思路
- 寻找左边界
(1) 我们注意到以左边界划分的两个区间的特点：
- 左边区间 [left, resLeft-1] 都是小于的；
- 右边区间（包括左边界）[resLeft, right] 都是大于等于的。
- 因此，关于 mid 的落点，我们可以分为下面两种情况：
(1) 当我们的 mid 落在 [left, resLeft-1] 区间的时候，也就是 nums[mid] < target。说明 [left, mid] 都是可以舍去的，此时更新 left 到 mid + 1 的位置，继续在 [mid+1, right] 上寻找左边界； (2) 当 mid 落在 [resLeft, right] 的区间的时候，也就是 nums[mid] >= target。 说明 [mid+1, right]（因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时更新 right 到 mid 的位置，继续在 [left, mid] 上寻找左边界。
- 由此，就可以通过二分，来快速寻找左边界。
注意：这里找中间元素需要向下取整。
因为后续移动左右指针的时候： (1) 左指针：left=mid+1，是会向后移动的，因此区间是会缩小的; (2) 右指针：right=mid，可能会原地踏步（比如：如果向上取整的话，如果剩下 1, 2 两个元素，left == 1，right == 2，mid == 2。更新区间之后，left, right, mid 的值没有改变，就会陷入死循环）。
因此一定要注意，当 right = mid 的时候，要向下取整。
1.2.2 寻找右边界思路
- 寻找右边界： (1) 用 resRight 表示右边界； (2) 我们注意到右边界的特点：
- 左边区间（包括右边界）[left, resRight] 都是小于等于的；
- 右边区间 [resRight + 1, right] 都是大于的。
- 因此，关于 mid 的落点，我们可以分为下面两种情况：
(1) 当我们的 mid 落在 [left, resRight] 区间的时候，说明 [left, mid-1]（mid 不可以舍去，因为有可能是最终结果）都是可以舍去的，此时更新 left 到 mid 的位置； (2) 当 mid 落在 [resRight + 1, right] 的区间的时候，说明 [mid, right] 内的元素是可以舍去的，此时更新 right 到 mid-1 的位置。
- 由此，就可以通过二分，来快速寻找右边界。
注意：这里找中间元素需要向上取整。
因为后续移动左右指针的时候： (1) 左指针：left=mid，可能会原地踏步（比如：如果向下取整的话，如果剩下 1, 2 两个元素，left == 1，right == 2，mid==1。更新区间之后，left, right, mid 的值没有改变，就会陷入死循环）； (2) 右指针：right=mid-1，是会向前移动的，因此区间是会缩小的。
因此一定要注意，当 left = mid 的时候，要向上取整。
1.3 二分查找算法总结
请大家一定不要觉得背下模板就能解决所有二分问题。二分问题最重要的就是要分析题意，然后确定要搜索的区间，根据分析问题来写出二分查找算法的代码。
