二分查找常见需求(持续更新中)

1.找到tmp中大于等于target的最小下标

当然如果不存在就返回tmp.length。

   public int binarySearch(int[] tmp, int target) {
        int l = 0, r = tmp.length - 1;
        if(tmp[r] < target) {
            return r + 1;
        }
        while(l < r) {
            int mid = l + (r - l) / 2;
            if(tmp[mid] < target) {
                l = mid + 1;
            } else if(tmp[mid] == target) {
                r  = mid;
            } else if(tmp[mid] > target) {
                r = mid;
            }
        }
        return l;
    }

①首先为什么用l

②为什么r=mid(而不是r=mid-1)呢？因为我们要找的是大于或等于target的最小下标，所以右区间收缩时不能忽略掉mid。

可应用的题目：绝对差值和

2.找到times中小于或者等于t的最大下标

   public int binarySearch(int[] times, int t) {
        int l = 0, r = times.length - 1;
        while(l < r) {
            int mid = l + (r - l + 1) / 2;
            if(times[mid] < t) {
                l = mid;
            } else if(times[mid] == t) {
                l = mid;
            } else if(times[mid] > t) {
                r = mid - 1;
            }
        }
        return l;
    }

①为什么要mid = l + (r - l + 1) / 2？因为mid=(l+r)/2是向下取整，找的是左边界，会出现 mid = l的情况，会导致 l= mid = r-1，后续会进入死循环,一直保持这样的值。需要补加1取右边界。举个直观的例子：假设 l= 3, r= 4, mid = (l+ r) >> 1 = 3，如果 mid 是合法值，l= mid = 3，范围 [3, 4] 没有变，永远循环下去，如果改成mid = (l+ r + 1) >> 1 = 4，那么满足l=mid=r=4,退出循环。

②为什么用l

③为什么l=mid(而不是l=mid+1)呢？如果t在(times[mid], times[mid+1])之间的话，如果把l提到mid+1的位置显然就越过了正确答案mid，所以就要设置l=mid。

 可应用的题目：在线选举 、和为K的最少斐波那契数字数目

3.得到preSum中大于k的最小下标

   int binarySearch(int[] preSum, int target) {
        int l = 0, r = preSum.length - 1;
        while(l < r) {
            int mid = l + (r - l) / 2;
            if(preSum[mid] > target) {
                r = mid;
            } else if(preSum[mid] == target) {
                l = mid + 1;
            } else if(preSum[mid] < target) {
                l = mid + 1;
            }
        }
        return l;
    }

①首先为什么用l

②为什么r=mid(而不是r=mid-1)呢？因为我们要找的是大于target的最小下标，所以右区间收缩时不能忽略掉mid。

 可应用的题目：找到需要补充粉笔的学生编号