今天突然想起来二分查找 求mid中间值会溢出的问题，便查找资料和自己思考记录一下这个问题。
二分查找时，我们往往会见到以下三种方法来求mid中间值
1.正常思路
mid = (left + right) / 2;2.防溢出写法
mid = left + (right - left)/2;
3.位运算 也是防溢出 无符号位元素符的优先级较低，所以括起来
mid = left + ((right - left)>>2);
那么为什么第一种方法会溢出呢？
我之前学二分的时候，当时是两种写法都有人用，但是第二种方法说是可以防止溢出，我当时也没有在意，今天早上醒来打开手机看见二分，突然想到这个问题了，所以想记录一下这个问题；
1.第一种方法可能会溢出原因
一般我们都是定义左边界（left）和右边界（right）都使用 int 类型，如果 left 和 right 足够大，mid = (left + right)/2，可能会由于 left+right 导致 int 数据类型越界。
int占用4字节32比特时的取值范围为 -2147483648～2147483647 假设left right 为1073741824
加在一起 left+right = 2147483648 超过了int的最大范围 此时就溢出了
如果超出int的最大范围 那么结果变成负数，（原本我不太理解为什么超出范围会变成负数，在网上查找资料了解到：
十进制数字存储在计算机时要转换为二进制。数字在累加的时候会不断进位，超过最大范围时符号位就变成了1，1表示的是负数，计算机就理解成这是个负数了（为原码，补码、反码部分的知识））
如下面这个例子
#include<iostream>
using namespace std;
int main()
{
int left = 1073741824;
int right = 1073741824;
int result1 = (left + right) / 2;
int result2 = left + (right - right) / 2;
cout << "result1：" << result1 << endl;
cout << "result2：" << result2 << endl;
system("pause");
return 0;
}
//运行结果
result1：-1073741824
result2：1073741824
而写成第二种方法 mid = left +（right -left)/2 的就会相对安全，（right - left）使用减法不会超出最大的整型范畴；给第二种方法通分一下就和第一种方法的式子一样。
写成第三种方法 mid = left +((rightt-left)>>2) 位运算，（效率是挺高的，就是嘛，不易懂hh）>>表示右位移运算符，把操作数的二进制码右位移指定位数，左边空出来的位以原来的符号位填充。原来是负数就填充1，原来是正数就填充0。符号位不变。
下面附二分板子（左闭右闭型，个人喜欢这种嘿嘿）
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
if (nums[middle] > target) {
right = middle - 1; // target 在左区间，所以[left, middle - 1]
} else if (nums[middle] < target) {
left = middle + 1; // target 在右区间，所以[middle + 1, right]
} else { // nums[middle] == target
return middle; // 数组中找到目标值，直接返回下标
}
}
// 未找到目标值
return -1;
}};
先这样啦~
