给大家出算法题 - 爱好C语言的同学进

综合教程

证书都是骗人的！

kgd7558

点评kgd7558同学的作品：

from = (from + to) / 2;

这句有问题哦。问题是什么呢？如果数组很大，from ...
无线狂人 发表于 2010-6-23 09:50

以上为个人见解,如有不足,请指正:

1、任何类型变量，它的表示范围都是有限的。
    我们写程序时所采用的数据类型取决于数据的取值范围，
    在数据范围满足情况下，选用数据类型参考如下两点：
            考虑优先选用占内存小的数据类型，这样可以节省内存
            考虑优先选用与cpu对齐的数据类型，这样处理速度最快
    在未知范围情况下：
            考虑选用表示范围最大的数据类型，以免变量益出
    以上几点属于代码编写问题

2、我们这里讨论的是算法
    能够简单明了地表示我们想法的代码我觉得就可以了，
    因为每一种算法，一旦使用代码示表示出来时，这就决定了它只能在某种范围内是有效的，
    而在某种范围之外，就变得无效。回到你所指的问题：
    from = (from + to) / 2;
    我们当然可以改成: from = (from / 2 + to / 2); 很明显会比上一句要好一些，
    但是既然能那样改，也可以这样改吧：from = (from >> 1 | to >> 1);  也很明显，又比上句要好，因为逻辑操作比较快。
    如果再极端点，我们这里可以插入汇编代码去实现，这样速度更快。
    我们回过头来对比这几种代码时：很明显是 from = (from + to) / 2; 最简单明了的吧？
    当然，如果是实际应用的话，当然是要考虑代码的优化问题，可我们这里只是讨论算法。

无线狂人

以上为个人见解,如有不足,请指正:

1、任何类型变量，它的表示范围都是有限的。
    我们写程序时 ...
kgd7558 发表于 2010-6-23 18:55

呵呵

其实这个bug是历史上一个很著名的关于二分的bug，详见：
http://www2.matrix.org.cn/resource/news/Joshua+Bloch+Bug_768.html

在一般情况下, 这个语句是不会出错的, 但是, 当low+high的值超过了最大的正int值 (231 - 1) 的时候, mid会变成负值。

改也很简单，直接 (from + to) >> 1

痴情潇湘

LZ是天才，坚定完毕

天堂雪

支持，赞一个

深水火焰

不错 支持一个了