二分搜索模板
给一个有序数组和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回-1
模板四点要素
-
1、初始化：start=0、end=len-1
-
2、循环退出条件：start + 1 < end
-
3、比较中点和目标值：A[mid] ==、 <、> target
-
4、判断最后两个元素是否符合：A[start]、A[end] ? target
时间复杂度 O(logn)，使用场景一般是有序数组的查找
注意：模板和它们的差异已被彩色标注如下。
二分搜索模板
模板１：
１、 循环条件中包含了left == right 的情况， 则我们必须在每次循环中改变left 和 right的指向，以防止进入死循环
２、 循环的终止条件包含：
- 找到了目标值
- left > right （这种情况发生于当left, mid, right指向同一数时，这个数还不是目标值，则整个查找结束。
３、 left + ((right - left)// 2)对于目标区域长度为奇数而言， 是处于正中间的， 对于长度为偶数而言，是中间偏左的。
因此左右边界相遇时只会以下两种情况：
- left/ mid , right (left, mid 指向同一个数， right指向mid的下一个数)
- left/mid/right (left, mid, right 指向同一个数)
即因为mid对于长度为偶数的区间总是偏左的，所以当区间长度小于等于２时， mid总是和left在同一侧。
模板２：
二分查找左边界
利用二分法查找左边界是二分查找的一个变体， 应用它的题目包含以下几种特征：
- 数组有序，但包含重复元素
- 数组部分有序，且不包含重复元素
- 素组部分有序，且包含重复元素
这 3 个模板的不同之处在于：
左、中、右索引的分配。
循环或递归终止条件。
后处理的必要性。
模板 #1 和 #3 是最常用的，几乎所有二分查找问题都可以用其中之一轻松实现。模板 #2 更 高级一些，用于解决某些类型的问题。
这 3 个模板中的每一个都提供了一个特定的用例：
模板 #1 (left <= right)
二分查找的最基础和最基本的形式。
查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。
模板 #2 (left < right)
一种实现二分查找的高级方法。
查找条件需要访问元素的直接右邻居。
使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
保证查找空间在每一步中至少有 2 个元素。
需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。
模板 #3 (left + 1 < right)
实现二分查找的另一种方法。
搜索条件需要访问元素的直接左右邻居。
使用元素的邻居来确定它是向右还是向左。
保证查找空间在每个步骤中至少有 3 个元素。
需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。
时间和空间复杂度：
时间：O(log n) —— 算法时间
因为二分查找是通过对查找空间中间的值应用一个条件来操作的，并因此将查找空间折半，在更糟糕的情况下，我们将不得不进行 O(log n) 次比较，其中 n 是集合中元素的数目。
为什么是 log n？
二分查找是通过将现有数组一分为二来执行的。
因此，每次调用子例程(或完成一次迭代)时，其大小都会减少到现有部分的一半。
首先 N 变成 N/2，然后又变成 N/4，然后继续下去，直到找到元素或尺寸变为 1。
迭代的最大次数是 log N (base 2) 。
空间：O(1) —— 常量空间
虽然二分查找确实需要跟踪 3 个指标，但迭代解决方案通常不需要任何其他额外空间，并且可以直接应用于集合本身，因此需要 O(1) 或常量空间。