||
二分一般分为3种情况:
第一,满足条件的第一个;第二,不满足条件的第一个;第三:满足条件的最后一个(可以由第二种情况-1得到,左边界要特判一下)
所以可能的解范围是[0,len](闭区间),因此,将 l = 0, r = len
三种情况的框架是一样的:
l = 0, r = len;
while (l < r) {
mid = l + ( (r-l) >> 1 );
if (ok(mid)) { // (1)
l = mid +1; // l 始终保存正确结果
} else {
r = mid;
}
}
return l; //(2) 第三种为return l-1;
这三种情况,只需要改(1)和(2)两处,改动第一次的规则就是使l 始终保存正确结果(或对于第三种情况,正确结果加1)。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-24 14:24
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社