二分法中的mid溢出处理

    技术2022-07-10  100

    在使用二分法过程中常常需要算mid的值,常见的算mid的方法就是 mid = (left +right)/2 当处理比较长的有序数组时,left与right比较大,容易造成溢出,产生错误,比较常见的处理是 mid = left+(right - left)/2,从而避免了可能出现的溢出。 另外 mid不一定等于 left/2+right/2,因为int/int 仍然为int ,没有小数部分,所以两边等式不一定成立。 例如 : left = 3 ,right =5, left/2+right/2 = 3 ,但是 (left+right)/2=4

    Processed: 0.021, SQL: 9