二分查找
1.理解
本质：二段性
首先我们需要打破我们的固有思维：二分查找不是只能使用在有序数组上！！！它使用的最本质的因素是因为具有二段性。
不只是只有有序才能使用二分，而是只要有二段性就能使用二分。
那么什么是二段性呢？
二段性可以理解成将一段区间划分成为两部分，这两部分都有一个各自的特点。
2.三种模板
2.朴素模板
该模板最常用于找一个特有的位置，即只有一个满足条件的情景。
int left, right; //定义左右指针
while(left <= right)
{
int mid = left + (right - left) / 2; //防止溢出
if(...) right = mid - 1;
else if(...) left = mid + 1;
else return mid;
}
注意事项
（1）循环条件
left <= right ，因为left = right的时候也需要判断该点符不符合题意要求。
（2）防止溢出
如果直接（left + right）/ 2的话，那么当left和right过大时就会超出int存储的范围，因此使用减法，来确保没有溢出。right - left为所要查找区间的长度，再除以2就是区间长度的一半，这样就可以找到中间位置。
3.左端点模板
通常用于所查找区间内多个值都符合要求时，该区间的最左边端点。常见于一部分区间小于，一部分区间大于等于这种情形。
while(left < right)
{
int mid = left + (right - left) / 2;
if(...)
left = mid + 1;
else
right = mid;
}
注意事项
1.为什么right = mid 而不是mid - 1
因为mid处的值也可能符合题目要求
2.求mid的时候，没有+1（此处可以结合下面例题理解，例题有详细解释）
此做法是为了防止死循环。如果区间只剩2个值，如果不加一就是取的左边的点，这样left就会移动，如果+1之后，right = mid就会一直是右边的点，那么right就不会移动，造成死循环。
3.对于left = right的情况，再根据题意来判断从而特殊处理。
4.右端点模板
通常用于所查找区间内多个值都符合要求时，该区间的最右边端点。
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(...)
left = mid;
else
right = mid - 1;
}
注意事项
1.为什么left = mid 而不是mid +1
因为mid处的值也可能符合题目要求
2.求mid的时候，有+1（此处可以结合下面例题理解）
为了防止死循环。如果区间只剩2个值，如果不加一就是取的左边的点，而左端点处left可能会一直不移动，这样就会造成死循环。
3.对于left = right的情况，再根据题意来判断从而特殊处理。
3.典型例题
3.1题目要求
3.2题目解析
由于题目说明为非递减数组，且使用O(logN)的时间复杂度解决，因此使用二分查找。查找满足条件的元素的第一个和最后一个位置，本质就是找到其左端点和右端点，直接套入模板即可。
3.3实现思想
方便叙述，使用x 表⽰该元素， resLeft 表示左边界， resRight 表示右边界。
寻找左边界思路
我们注意到以左边界划分的两个区间的特点：
（1）左边区间 [left, resLeft - 1] 都是小于x的。
（2）右边区间（包括左边界） [resLeft, right] 都是大于等于 x 的；
因此，关于 mid 的落点，我们可以分为两种情况。
情况一：
当我们的 mid 落在[left, resLeft-1]区间的时候，也就是 nums[mid] < target。说明[left, mid]都是可以舍去的，此时更新 left 到 mid + 1 的位置，
情况二：
继续在 [mid + 1, right] 上寻找左边界；当 mid 落在 [resLeft， right] 的区间的时候，也就是 nums[mid] >= target。说明 [mid + 1, right]（因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时更新 right 到 mid 的位置，继续在 [left, mid] 上寻找左边界；由此，就可以通过⼆分，来快速寻找左边界；
注意：这⾥找中间元素需要向下取整。（即求中点时是否+1）
因为后续移动左右指针的时候：
左指针： left = mid + 1，是会向后移动的，因此区间是会缩小的；
右指针： right = mid ，可能会原地踏步（⽐如：如果向上取整的话，如果剩下1,2 两个元素， left =1，right = 2，mid = 2。更新区间之后，left，right，mid 的值没有改变，就会陷⼊死循环）。
因此⼀定要注意，当 right = mid 的时候，要向下取整。
寻找右边界思路：
我们注意到右边界的特点：
左边区间 （包括右边界） [left, resRight] 都是小于等于x的；
右边区间 [resRight+ 1, right] 都是大于x 的；
因此，关于mid 的落点，我们可以分为下⾯两种情况：
情况一：
当我们的 mid 落在 [left, resRight] 区间的时候，说明 [left, mid - 1]（ mid 不可以舍去，因为有可能是最终结果） 都是可以舍去的，此时更新 left 到 mid的位置。
情况二：
当 mid 落在 [resRight+ 1, right] 的区间的时候，说明 [mid, right] 内的元素
是可以舍去的，此时更新 right 到 mid - 1 的位置；由此，就可以通过⼆分，来快速寻找右边界；
注意：这⾥找中间元素需要向上取整。
因为后续移动左右指针的时候：
左指针： left = mid ，可能会原地踏步（⽐如：如果向下取整的话，如果剩下1,2 两个元素， left = 1， right = 2，mid = 1 。更新区间之后， left，right，mid 的值没有改变，就会陷⼊死循环）。
右指针： right = mid - 1 ，是会向前移动的，因此区间是会缩⼩的；
因此⼀定要注意，当 right = mid 的时候，要向下取整。
3.4代码实现
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size() == 0) //处理特殊情况
return { -1, -1 };
int left = 0, right = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] < target)
left = mid + 1;
else //nums[mid] > target
right = mid;
}
if(nums[right] != target)
return { -1, -1};
int begin = left;
right = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(nums[mid] <= target)
left = mid;
else
right = mid - 1;
}
return {begin, right};
}
3.5注意事项
1.特殊情况
如果为空数组，则会发生越界--->特殊处理
2.如果压根没有这个元素，那么就无法找到左端点，则直接判断，如果没找到，返回即可。