讨论一下如何写 binary Search （比如lower/uppper bound)

每次写lower/upper bound类似的代码， 都纠结于  (1)  l，r是写成 l<r or l <=r,

  (2) return l, or r ? or m ? or others ?

举个例子啊： lower bound， (find the index of the larget key which is less or equal to the given key)
```
int lower_bound(int[] arr, int l, int r, target) {
   int largestIndex = -1;
   while(l <=r) {
       int m = l + (r-l)/2;
       if (arr[m] == target) {
          largestIndex = Math.max(largestIndex, m);
          r = m - 1;
       } else if (arr[m] > target) {
          r = m - 1;
       } else {
          largestIndex = Math.max(largestIndex, m);
          l = m + 1;
       }
   }
   return largestIndex;
}
```
这个是我自己喜欢用的版本。。 但是感觉用了Math。max。。 感觉不够精简。。。

大家一半都怎么写这个代码呢？  
可否一起讨论一下怎么最好。。

这个问题下面的第一个回答特别好，二分查找有几种写法？它们的区别是什么？ https://www.zhihu.com/question/36132386
从为什么左闭右开 和 while loop的循环不变量 - loop invariants的角度的分析了为什么这样写。

我一般都用同一个模板，左闭右开
while (l < r) {
    m = l + (r - l) / 2
    if (f(m)) {
        r = m
    } else {
        l = m + 1
    }
}
这样可以求出令 f(l) == true 的l 的最小值，如果l == r则不存在

在leetcode里这个方法几乎可以ac所有的二分题.p.s. 如果觉得有用的话求米

其实你可以理解一下什么叫lower bound。lowerbound其实指的是满足某种条件的下界。
二分查找可以理解成找到一个边界，左边符合某个条件，右边符合另一个条件。
lower bound指的就是右边的最左端点。

1. while (left < right) {
   
2.     int mid = (left + right) / 2;
   
3.     if (arr[mid] < target) {
   
4.         left = mid + 1;
   
5.     } else {
   
6.         right = mid;
   
7.     }
   
8. }
   
9. return left;

复制代码

这段代码求的其实是arr[j] >= target的最小下标。也就是lower bound。
为什么left要等于mid加一呢，因为mid不满足这个条件，所以mid不会成为最终的分界点。
right确实是可以成为分界点的。

网上有不同人总结的不同模版。你找其中一种你同意的风格，然后彻底理解，把它做成自己的模版，然后就再也不怕binary search了。别自己总结，因为你会漏掉很多情况的，相信我。（或者你自己总结后对比不同人别人总结的，你就明白你漏掉什么了）

你可以去搜一下九章的二分模版，退出的时候再做一次判断

https://leetcode-cn.com/circle/article/LXYqmM/

搜 c++ lower_bound函数  或者看下花花酱的 别自己总结了  既然你现在都还在搞清楚二分模版

我自己也是对binary search有很多疑问。有时候if statement的顺序也有影响。还有时候l = mid + 1 还是l = mid分不清（我知道这个概念，但是有时候明明是l = mid + 1更准确，但是用l = mid可以得到更精简的代码）

ranbaoranbao 发表于 2020-8-13 13:07
https://leetcode-cn.com/circle/article/LXYqmM/

这个总结非常不错！尤其是loop之后对left，right指针的分析。。

你可以参考下python bisect库的实现， 我觉得挺不错的


def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    a[i-1]<=x<a[i]
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] <= x: lo = mid+1
        else: hi = mid
    return lo

def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.

    a[i-1]<x<=a[i]
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

马克儿zszszszs