题解 | #二分查找-II#
二分查找-II
http://www.nowcoder.com/practice/4f470d1d3b734f8aaf2afb014185b395
二分查找的两个模板
- 循环必须是l < r
- check() 判断是否符合条件
- 如果 出现
r = mid - 1
, 则前面求mid 需要 加1- 出循环一定是
l == r
, 所以结果使用那个都行
找出 >=
给定数的第一个位置(满足条件的第一个数)
public static int binSearch(int[] num, int l, int r) { while(l < r) { int mid = l + r >> 1; if(check()) { r = mid; } else { l = mid + 1; } } }
找出 <=
给定数的最后一个数 (满足某个条件的最后一个数)
public static int binSearch(int[] num, int l, int r) { while(l < r) { int mid = l + r + 1 >> 1; if(check()) { r = mid - 1; } else { l = mid; } } }