二分答案需注意的细节问题

[php] l:=0;r:=max; while l<=r do begin mid:=(l+r)shr 1; if check(mid)then r:=mid-1 else l:=mid+1 end; ans:=l; [/php] 因为循环结束后有两种可能： 上一次循环 设r=l+1 mid=[(2l+1)/2]=l 若check(mid)=true r=l-1 则 l>r 答案为l 若check(mid)=false l=l+1 则l=r 答案为l 所以结束时有两种情况都要考虑到，所以要写 while l<=r do 而while l<>r do 只考虑了l=r的情况 因为最后可行解都为l，所以在循环结束后答案就是l。 另外根据是要尽量往右取还是尽量往左取来选择最后解，往右取取右解，反之亦然。