首页 > 代码库 > 二分查找收集
二分查找收集
二分查找有很多种写法…对不同的功能也有不同的写法，比如找最左边的相等的数、小于它的最大的数、大于它的最小的数等等……我写的时候总是特别蛋疼。于是来收集一下，以后要用二分查找的时候，新的写法我就拿来放在这里。
在升序中找比a[i]大的第一个（比a[i]大的最小的一个）（数据要保证必有比a[i]大的，不然l会跳到sn）（用于LIS的nlogn写法中）
1 l=0;2 r=sn-1;///二分找比a[i]大的第一个（s[sn-1]肯定比a[i]大，l不会加爆）3 while(l<=r) {4 mid=(l+r)>>1;5 if(s[mid]>a[i]) r=mid-1;6 else l=mid+1;7 }8 s[l]=a[i];
找符合check(mid)的最小的数（咦，好像和上面那个一样啊……上面那个也可以说成“找符合s[mid]>a[i]的最小的mid”……）（这个也是范围内必须要有，不然l会跑到爆）（用于Levko and array）
1 l=0;2 r=2000000000;3 while(l<=r)4 {5 mid=(l+r)>>1;6 if(check(mid)) r=mid-1;7 else l=mid+1;8 }9 printf("%I64d\n",l);
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。