昨天我们讲了一个二分的题目 《 一天一算法题，二分法的妙用 》，有人留言说算法的进步不如硬件的进步，觉得算法没卵用，我们先看看今天这个题目，然后再回头看看这个观点。我们今天继续进一步讨论一个二分的问题。这是一道谷歌的面试真题。
有一个长度为n的单调上升队列，我们要找到距离k最近的c个数。输出这 c个数中最小与最大的值。如果存在多个答案，输出更小的。
例子 1 2 3 4 8 10 11， k = 7, c = 3, 与7最近的3个数是 4,8,10,输出[4, 10]。
思考：
这个题目，最简单地有O(n)的算法 。这个我们就不讨论了，相信大家都懂。我们来看看算法的优化。
首先我们进行问题分解，我们先解决一个更简单地问题：
在一个单调上升的队列，找到一个距离k最近的数
这个问题，相信很多人都能一眼就解决问题，这就是经典的二分查找的题目。
然后我们再找距离k最近的c个数。我们有O(c)的算法。
1. 我们通过二分法找到8
2. 然后我们左右进行扩展，扩展c次。
这个算法的总复杂度为lg(n) + c， 如果c很大的时候，会退化成O(n)
我的一个好朋友在最近的一次面试中也只是想到这一步了。那么这一步如何进行优化呢？
我们依然可以进行二分！这里二分是非常巧妙的。（毕竟是谷歌的面试题呀）。
当我们找到1个离k最近的数之后，记下他的坐标x，必定存在至少p = (c - 1) / 2个数,这里的除法向上取整。在x的左边，或者x的右边！我们通过一个例子来看一下。这里我们要找距离11最近的9个数
通过比较，7比19离11更接近，于是我们选择了7-10；我们还需要继续选择4个数。
通过比较，15比5离11更近，于是我们选择了13与15.还需要再选两个。
接下来还要再选两个，比较简单就不画图了。最后选择了【5,15】。
这里我还是要再感叹一下，谷歌的面试题真的很不错，通过这样子进行优化后，变成了log(n) + log(c)。
总结：
在这里，我们认识了二分法的一个其他的例子！二分法可不止用在单调队列中的查找。
这个题目，其实是一个现实问题的简化。现实中，我们经常需要找，某个东西最相近的若干东西。例如淘宝会跟你推荐这个商品相似的产品。
很 多人会问，到底O(n)跟O(log(n)+log(c))到底有多大区别呢？一个O(n)的请求比如需要400ms，第二个方法一般不到10ms，可能 一个请求不能感受出来，但是如果有连续多次询问呢？算法的优势就显现出来！这就是算法的魅力！当然，我们也要考虑网络呀，系统IO等其他的性能。
原创不易，欢迎大家关注我的头条号，也可以关注我的微信公众号（ddpcyh）,后续会提供算法学习资料，一起来学习算法吧。
