hmi*_*mir 7 java algorithm binary-search
我正在学习算法/大o,我只是对此感到好奇.
指某东西的用途
mid = (low+high)/2;
为了获得二进制搜索算法的中点,通常不鼓励因为可能存在溢出错误.为什么会导致溢出错误,怎么办？
mid = low + (high-low)/2;
防止这个错误？
谢谢.
在第一种情况下,你计算的值(低+高)可能太大而不适合int,如果低和高都足够大(比如两者都等于2 ^ 30 + 1 /甚至更大/) .在第二种情况下,你不计算(低+高),你做一个小技巧,你通过表达式(高 - 低),该表达式相对于int溢出更安全.
但是,如果你没有一个大小超过2 ^ 30的数组(无论如何这是一个非常庞大的数组),我看不出即使使用第一个表达式你也会遇到int溢出.所以我会在大多数情况下使用第一个而不用担心.
| 归档时间： |
|
| 查看次数： |
2116 次 |
| 最近记录： |