Binary Search的总结帖

可以自己推一下，如果遵循下面的基本原则，就只需要一种写法。推导过程就省略了，建议大家举几个例子帮助理解，以免理解错误，毕竟自然语言是有歧义的。

基本原则就是：

1. 使用闭区间 [L, R] (用左闭右开区间也可以，只不过要相应地修改下面的几个原则)
2. 永远使用 while(L <= R)
3. 永远使用 L = mid + 1; R = mid - 1
4. 退出while循环之后，L和R一定满足 L = R + 1
5. return L 或者 return R

第5条需要自己现场稍微推一下，但是不难。基本规律是, 如果是按照下面的代码（假设数组 a 是单调递增序列）

1. if(a[mid] < target)  L = mid + 1;
   
2. else   R = mid - 1;

复制代码

那么，退出while循环之后，L 的位置一定在所有"＜target" 的数的右边；R的位置一定在所有 "≥target" 的熟的左边。也就是说，a[R] <= target < a[L]

换言之，使得 L = mid  + 1 的 if 语句用了什么条件，在退出while循环之后，所有满足这个条件的数全都在 L 的左边；使得 R = mid - 1 的 if 语句用了什么条件，在退出while循环之后，所有满足这个条件的数全都在 R 的右边。并且 L = R + 1

所以，如果把上面的代码改成

1. if(a[mid] <= target)  L = mid + 1;
   
2. else   R = mid - 1;

复制代码

退出while循环之后，最后会得到，a[R] < target <= a[L]，L = R + 1

如果知道这样的表达式，最后应该return L 还是 return R，就根据题目的具体要求来看了。

写的不错，不过我觉得个人的话记住自己喜欢用的一个模板就行，以后都是往里面套，基本数不会出错。但是如果你是全都用，那是非常容易混淆的。后面基本数我就用左闭右开的那个模板，基本没犯错。

幸苦楼主了，要是论坛支持markdown就更好了😂

markkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk

666 mark

感谢！！

感谢！！

@loonreg  总结的太好了。非常感谢

loonreg 发表于 2019-7-5 19:26
可以自己推一下，如果遵循下面的基本原则，就只需要一种写法。推导过程就省略了，建议大家举几个例子帮助理 ...

刚看到这个总结，第一种情况写反了，if(a[mid] < target)  L = mid + 1; else   R = mid - 1; 找最左边的插入点，退出while循环之后: a[R] < target <= a[L]。

太赞了，谢谢楼主分享！！！！