算法:使用二分查询技巧 取中间值为啥是l+(r-l)/2而不是(l+r)/2?

1.溢出问题

比如:Java的世界里Int类型最大值是: Integer.MAX_VALUE = 2147483647

        System.out.println("Integer.MAX_VALUE = " + Integer.MAX_VALUE);
        int left = 2147483647;
        int right = 2147483647;
        int result = (left+right)/ 2;
        System.out.println("result = " + result);
        
        int result2 = left+(right-left)/2;
        System.out.println("result2 = " + result2);

此时可以在脑中运行一遍,看是否与下面电脑运行的结果相符?

Integer.MAX_VALUE = 2147483647
result = -1
result2 = 2147483647

结论:(left+right)/2容易导致溢出,而left+(right-left)/2很好的避免的溢出

2.右移>>优先级问题

先看一下的例子

        int i = 12;
        int d = 16;

        int res = i + ((d - i) >> 1);
        System.out.println("res = " + res);

        int e = 16;
        int res2 = i + (e - i) >> 1;
        System.out.println("res2 = " + res2);

实际运行结果如下:

res = 14
res2 = 8

原因:右移>>的优先级比加号+还低,所以注意:再使用右移运算符>>注意使用()括起来

3.关于负数问题

        int le = -10;
        int ri = -3;
        int ave1 = (le + ri) / 2;
        int ave2 = le + (ri - le) / 2;
        System.out.println("ave1 = " + ave1);
        System.out.println("ave2 = " + ave2);

结果:

ave1 = -6
ave2 = -7

原因:

• int/2的取整是向下取整,在正数的时候,参考系是正向横向轴,l+(r-l)/2或者(l+r)/2计算结果没有区别
• 在负向横向轴的情况下,l+(r-l)/2或者(l+r)/2计算结果有区别,计算后的结果是以left为边界相加,因为int/2的向下取整问题,导致计算结果的值小一些
• 导致正向和和负向结果可能不一致的原因是绝对参考系和相对参考系方向不一致的时候,会有1的差距

如果要想两个公司结果保持一致,可以这样写,代码如下:

        int ave3 = ri + (le - ri) / 2;
        System.out.println("ave3 = " + ave3);

运行结果如下:

ave3 = -6

4.负数的右移计算,容易出现诡异的bug问题

        int x = -9;
        int aa = x / 2;
        int bb = x >> 1;
        System.out.println("aa = " + aa);
        System.out.println("bb = " + bb);

实际运行结果:

aa = -4
bb = -5

原因:

int类型的取整是向0取整,即使被取整的数绝对值变小

而右移是向下取整,即使被取整的数值变小

所以对于正数时两者相同,而到了负数则变大

小结:在对负数进行右移运算时候,运算计算跟平时大脑运算的结果不一样,所以一般情况下乖乖用/除号,省得考虑不周,出现诡异的bug

5. 扩展知识

二分定义

二分查找()百度百科):二分查找也称折半查找()Binary Search),它是一种效率较高的查找方法.但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列.

上述的定义只是狭义上的二分查找定义,在上述定义中提到了一个概念:有序,但实际上,我们只需要让线性表满足二段性即可使用二分.

二段性那么,什么是二段性呢

所谓二段性，就是在线性表中有一个元素，使得该元素的左侧满足性质1，右侧满足性质2。

举个例子，有一个数组nums = 4, 5, 6, 7, 0, 1, 2，该数数组原本是严格递增的，但是被按照某个点旋转了一次。现在我们需要找出该数组的原始起点（当然，直接遍历一遍是一种有效但并不优美的做法）。在这例子中，起点当然是0了，并且我们通过观察可以发现，0的左侧满足所有的元素都大于等于nums0 = 4（性质1），而 0及其右侧元素都小于nums0 = 4（性质2）。那么此时，元素0就是让这个线性表具有二段性的元素之一（为什么说之一呢，因为例如7也能使该线性表具有二段性）。

为什么具有二段性就能使用二分呢？

还是拿上述例子进行说明，我们既然清楚了我们需要查找的元素具有二段性，那么，我们是否可以利用这个性质缩小查询范围以不断逼近并最终查询到这个元素呢？

利用二段性实现二分答案是肯定的。每一次，我们取整个线性表的中间元素（下标记为mid），判断numsmid满足性质1还是性质2。

如果满足性质1，则说明numsmid在目标元素的左侧，此时我们将区间左端点（l）移动到mid + 1(因为此时我们可以明确的知道numsmid并不是我们需要的元素)

如果满足性质2，则说明numsmid就是目标元素或是在目标元素右侧，此时我们将区间右端点移动到mid **

我正在参与2023腾讯技术创作特训营第四期有奖征文，快来和我瓜分大奖！