【二分查找】 二分查找mid值溢出问题

 今天突然想起来二分查找 求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;
}

};

先这样啦~

​