liyanbo的个人博客分享 http://blog.sciencenet.cn/u/liyanbo

博文

二分查找

已有 2220 次阅读 2016-11-6 11:26 |个人分类:算法|系统分类:科研笔记

二分一般分为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)。



https://blog.sciencenet.cn/blog-1515646-1013008.html

上一篇:C++基本概念
下一篇:python调用c++,java,python,shell程序
收藏 IP: 159.226.43.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-11-24 14:24

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部