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;elseright = 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;elseright = 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] > targetright = 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;elseright = mid - 1;}return {begin, right};}

3.5注意事项

1.特殊情况如果为空数组，则会发生越界--->特殊处理
2.如果压根没有这个元素，那么就无法找到左端点，则直接判断，如果没找到，返回即可。