灵神基础算法精讲-04-学习笔记

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

思路

利用数组是有序的这个性质，初始化两个指针，L为0，R为n-1，我们现在需要知道这个闭区间内的每个数和target的大小关系，即它是小于target还是大于等于target的，取中间的数和target进行比较，能够立刻知道数组中一半的元素和target的大小关系，所以取中间是最合适的。如果区间里面有偶数个数，则可以取左边的数，即 (L+R)/2 下取整。

左闭右闭，将 L 更新成 M+1，如果更新成 M 就变成左开右闭区间了，将 R 更新成 M-1。在最后一次更新时，R 已经跑到 L 的左边了，上面说的把 L 更新成 M+1，或者说把 R 更新成 M-1，这同时意味着一件事情，就是 L-1 指向的一定是小于 target 的，R+1 一定指向的是大于 target 的，它们两个被称为循环不变量，循环结束之后，R+1 就是答案。

做法

左闭右闭

初始化左右指针分别为0和n-1，循环继续条件为 left <= right，首先计算 mid = (left + right) // 2，如果 nums[mid] < target，则 left = mid + 1，否则 right = mid - 1，最后返回 L 或者 R+1。

左闭右开

初始化左右指针分别为0和n，循环继续条件为 left < right，首先计算 mid = (left + right) // 2，如果 nums[mid] < target，则 left = mid + 1，否则 right = mid，最后返回 L 或者 R。

左开右开

初始化左右指针分别为-1和n，循环继续条件为 left + 1 < right，首先计算 mid = (left + right) // 2，如果 nums[mid] < target，则 left = mid，否则 right = mid，最后返回 L + 1 或者 R。

拓展

上述做法求的是第一个 >= target的数，其还有三种变体。

>target

等价于 >= target+1

<= target

等价于 > target - 1

<target

等价于 >= target - 1