二分法(BinarySearch)，是一个简单却很容易写错的算法。据说，Jon Bentley（k-d tree的发明者）做过一次调查，90%的程序员，花上几个小时，也写不出一个正确的二分算法。我写了几个，发现成败在细节上。后来总结出了一个经验，就是把重点放在二分法那个擦肩而过的美好瞬间。下面通过几个例子来体会。

找寻插入位置

1
2
3
4
5
6
7
8
9

说，你有一个整数数组，已经排序完毕，升序，并且没有重复的元素。
问，给你一个整数，求它在数组中的插入位置。

拿[1, 4, 7, 8]来说，
0 -> 0，
2 -> 1，
5 -> 2,
7 -> 2,
9 -> 4

我写了如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int searchInsert(int[] nums, int target) {
        int start = 0; 
        int end = nums.length - 1;
        while(start <= end) { 
            int mid = start + (end - start) / 2; 
            if(nums[mid] == target) {
                return mid;
            } else if(target > nums[mid]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return start;
    }
}

确保相遇

当start比end小或相等的时候，我们都继续找，而当start超过end，他们擦肩而过的时候，我们停止循环。为了避免他们停滞不前，每次我们要么增加start，要么减小end，确保他们擦肩而过。

擦肩瞬间

由于每次要么start增加，要么end减小，只有一方会发生变化，必定有一个瞬间，他们相遇落在同一个位置上。这次相遇是最令人心动的地方，也是该算法，最需要注意的地方。请问在上述代码中，从while循环出来的时候，为什么返回的是start，而非end？请认真思考一下，再看我的分析。

让我们把注意力放在他们擦肩相遇的瞬间，start和end站在了同一个位置，start看一下目标值和眼下的值，如果发现目标大，start往前一步，超越了end，新的start必定是插入的正确位置；如果发现目标小，start让end走一步，start留在了原地，正好占用当下的插入位置，因为要插的值正好比当下的小。

是不是这个瞬间很美好？

求平方根

1
2
3

求整数的平方根，结果要整数。比如：
sqrt(16) = 4,
sqrt(15) = 3 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int mySqrt(int x) {
        if(x == 0) return 0;
        if(x == 1) return 1;
        int start = 1;
        int end = x / 2;
        while(start <= end) {
            int mid = start + (end - start) / 2;
            int square = mid * mid;
            if(square == x) return mid;
            if(square > x || (square / mid != mid) ) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return end;
    }
}

为什么出了while循环，我们返回的是end？擦肩而过的瞬间发生了什么？

求区间的头和尾

1
2
3

说，有一个整数数组，按升序排序完毕
求，目标值得首次和最后出现的位置，找不到返回[-1, -1]。时间复杂度必须控制在o(logn)
比如在[1, 2, 3, 3, 3, 4, 4]求3的区间，答案是[2, 4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{
            searchLow(nums, target), searchHigh(nums, target)};
    }
    
    private int searchLow(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while(start <= end) {
            int mid = start + (end - start) /2;
            if(target <= nums[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        if(start > nums.length - 1) return -1;
        if(nums[end + 1] == target) return end + 1; //回头看
        return -1;
    }
    
    private int searchHigh(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while(start <= end) {
            int mid = start + (end - start) /2;
            if(target >= nums[mid]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        if(end < 0) return -1;
        if(nums[start - 1] == target) return start - 1;
        return -1;
    }
}

你能体会到擦肩而过的美妙吗？在找区间头的过程中，end在相遇的位置上看了一下目标值和眼下值，如果发现目标值小或正好，end就会往前走一步，翻过start。最后end回头看，那么相遇时的位置，要么区间头找到了，要么目标值不存在。

总结

二分法，是有规律可寻的，首先就是要确保start和end总有一方前进，进而确保擦肩而过跳出while循环。其次就是根据需求，决定在相遇的瞬间，是start还是end动。掌握了这个规律，你定能写出来正确的二分法。

法国工程师学位的我，后台开发六年有余。如今深深爱上了数学，感慨以前学得不够。

首先，无论是哪方面的程序员，都要大量的投资算法和数据结构。因为这是你的基本技能，就像棋手需要知道每个棋子的走法一样。在算法学习的过程中，你绕不过的就是衡量算法的效率，也就不可避免的学习Big O的知识。Big O，需要你了解函数和极限的一些知识，比如说，f(n) = O(g(n))是这样定义的，当n足够大的时候，你总可以找到一个常数c，使得c * f(n) >g(n)。除了效率，还有如何证明算法的正确性。这就要求掌握一些证明方法，比如反正法，递推归纳法。

其次，如果你遇到了性能方面的问题，需要降低延迟，增加吞吐的时候，你很有可能需要去设计高性能的队列系统，这时排队论的知识就显得尤为重要了。排队论要学好，概率论是基石。队列在计算机系统中随处可见，操作系统中的进程调度问题，基于队列解藕生产者消费者的架构问题等等。

接下来如果你对离散优化问题感兴趣，如说背包问题，旅行者问题，当你需要优化一个目标函数的时候，你往往会用到梯度下降法，而理解梯度下降法，对微积分要有很好的理解。更不用说在人工智能，机器学习领域，到处都得优化目标函数，降低预测误差，想走的远，是必须要有数学基础的。

然后再说一下，线性代数，特别是在人工智能里面，很多基本的模型都是线性的，你会随处看到矩阵的用处，单纯的只知道矩阵如何相乘是远远不够的，要理解的跟深入，矩阵是一个函数，用来转换矢量，既然是函数，就会具有很多函数的特点。你应该懂得如何证明 （矩阵甲 x 矩阵乙）x 矩阵丙 = 矩阵甲 x （矩阵乙 x 矩阵丙）

最后，说点我也没有搞明白的，分布式系统中的鼻祖级论文，Lamport的时间，时钟，和事件的顺序，据他所说是他从相对论中的时间和空间的关系中得到的灵感。由此可见，不仅是数学，物理也很重要。

总结一下吧，当时是学生的时候，学数学不知道怎么用，只知道考试，回想起来 ，如果应用场景更清晰的话，我会投入的更多。

数学学习资源

• 线性代数的本质 - 3Brown1Blue
• 微积分的本质 - 3Brown1Blue

入春以来，鼻子痒，堵，流鼻涕，像感冒一样，其实是过敏。看了个耳鼻喉的专家，她的一番话，竟让我联想到了软件开发中的测试问题。就像Dijkstra说的，测试只能表明Bug的存在，而非它们的绝迹。

过程是这样的，我做了一个抽血实验，指标说明我没有过敏。医生很耐心的跟我讲，抽血结果说你没过敏，并不代表你没过敏。因为抽血化验只针对一部分过敏原。结果是好的，只能说明你对这些物质没有过敏反应。并不能代表你对其他东西也不过敏。像什么狗毛了，猫毛了，花粉了什么的，并不在化验的范围内，所以你有可能对他们过敏。也没有必要做更多的测试，因为很可能你又测了十几种，还是没找到过敏原，也只能证明对这些测试的东西没反应，而说明不了全部。

话，绕来绕去，就是告诉我，我知道你对哪些东西不过敏，不知道你对什么过敏。这就像软件测试一样，你写了一个测试，我们只能知道，在这种情况下，软件会好用，但并不知道，在哪些情况下不好用。

我举个简单的例子，比如下面的冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13

public class BubbleSort implements Sorting {

    @Override
    public <T> void sort(T[] elems, Comparator<? super T> comp) {
        for (int out = elems.length - 1; out > 1; out--) {
            for (int in = 0; in < out; in++) {
                if (lessThan(elems[in + 1], elems[in], comp)) {
                    swap(elems, in, in + 1);
                }
            }
        }
    }
}

针对下面的输入，都能排好

1
2
3

Arrays.asList(2, 3, 4, 8, 5, 7, 1, 6);
Arrays.asList(2, 8, 3, 4, 5, 7, 1, 6);
Arrays.asList(5, 8, 4, 3, 2, 7, 1, 6);

但有一种情况排不好，你能看出来是为什么吗？

1

Arrays.asList(2, 3, 4, 8, 5, 7, 6, 1);

医生说，没必要做所有的测试，因为成本太大，并且不一定找到好的结果。但对软件测试而言，有没有好的办法呢。我是一个热情洋溢但比较笨的工程师，所以用了一种比较笨的方法，就是随机产生很多测试，暴力解决问题，这里你可以看得到，后来才意识到，在这种情况下，大家都在用一种叫基于属性的测试方法：Property-Based Test。有没有更暴力的呢，还真有，There are Only Four Billion Floats–So Test Them All!。

一个过敏测试，一个软件测试，看上去两个没有联系的东西，可认真比较后，却惊喜的找到了他们的共同点。类比之后，反而对Dijkstra的那句话有了更加深入的理解。

1. 服务精神：超越自我
2. 服务精神：反馈循环

上次说服务精神的时候，选择了超越自我作为切入点。这次想从反馈循环的角度来谈谈服务精神。先撂个包袱，曾经有一个同事走了，我问他为什么，他说，因为他写的代码，很快就能部署到生产环境，用在客户手里。

什么是反馈循环

反馈循环，说白了就是有去有回，有来有往。你提供了一个服务，想知道服务的质量好不好，你就会问客户，然后根据客户的反馈提升服务的质量，然后把更好的服务，再次提供给客户，往往复复，越来越好。举个例子，你下了馆子，点了个鱼香肉丝，吃完，服务员问你，好吃吗？你说肉有点少。服务员记下来了，告诉给了大厨。第二天，你来了，又点了一个鱼香肉丝，真的发现肉多了，你很高兴，从此就常来吃饭。多亏了你这样的客户，饭馆的生意越做越好。

程序员，也一样，你写了个代码，但是不知道好不好，就想问问客户体验怎么样。然而，到这一步，往往是悲剧，发现没人可问，因为没人用。这就是我今天所想说的。让我们看看反馈循环的缺失所带来的危害，还有如何避免。

有用就是有人用

我出个上联：有用就是有人用。你对个下联。请仔细思考一分钟再往下看。

我很笨，只能想到这个下联：没用就是没人用。真不是逗你玩，什么叫有用？！如果都没人用，还有什么好说的。道理很简单，可忽略了它，会有很多麻烦。不少初创公司就特爱犯这个错误。有一天，你有个好点子，激动的不行，拉上一些朋友，热火朝天的干了起来，憧憬着融资上市时的样子，干了好久，终于要问世了，然而发现，你做了一个没用的东西，对！一个没人用的东西。浪费了时间，感情，和精力。

一个没有服务精神的人，首先想到的不是他的服务对象（很可能想的是成功了怎么办呀），自然，也就不会想着去问回馈。等想起来了，发现已经走得太远了，做了一个没人用的东西。因此，要避免浪费时间，感情和经历，就要首先培养服务精神，搭建反馈循环。

搭建反馈循环

其实，这并不是一个新的话题。很多前辈在不同的领域已经做了很多研究。比如精益创业里的”构建-测试-学习“循环；测试驱动里的”红-绿-重构“循环；还有敏捷开发里的客户融入开发团队的做法；持续交付，等等。

在所有方法的背后，我所体会到的精髓就是服务精神，而服务精神的精髓就是先想到别人。

拿了工资就不算浪费生命吗？

再说最后一点吧，也是我工作六年多了，才有的感触，和服务精神有关系。很多大公司，他们的商业模式往往是经过验证的，肯定是有客户的，否则也不会活那么久，招那么多人。然而作为一个程序员，我们能碰到的往往是大山的一角。写出的代码，从你的文档编辑器到最终用户的手里，往往需要很久，短了几个月，长了可能几年，因为你的项目就是交付不了。这种情况下，我们是得不到用户反馈的。

我之前的想法是，这关我鸟事？工资照常发，代码就算没白写。可培养了服务精神之后，我改变了想法，会有点忧伤。你想想，你用了三年时间写出来的代码，没人用。对，没人用！你不觉得，你这三年可以做一些更有意义的事情吗？

如果有一天我换工作了，我想我的原因，应该和开头那同事说的一样。

1. 服务精神：超越自我
2. 服务精神：反馈循环

一位同事最近要离职了，去更远的地方。从他身上，我看到了很多闪光点，其中最亮的就是服务精神。餐厅里，小二接待食客，我们称之服务。作为程序员的我们，用代码给人带来便利，也是服务。

有服务精神的人，更愿意去挑战自我，超越自我。

同样是开发一个API，服务精神缺失的程序员，文档不写，测试没有，每个月能按时领工资，就心满意足了。

有一定服务精神的程序员，他会想到使用API的人。他会写个文档解释API的设计意图和使用方法。他会写一些单元测试，保证代码的正确性。达到这个阶段的程序员，已经可以算得上优秀程序员了。你可以看看周围的同事，有多少人练到了这个段位。

有强烈服务精神的人。他们会想的更远，更周到。就像你去海底捞吃火锅，在你等人的时候，人家怕你无聊，给你提供水果瓜子。这个阶段的程序员，非常注重用户的感受。他们首先要确保API可用易用性。其次，他们还会想到API的性能，让用户在这里花费的时间越少越好。最后，他们还会考虑，万一服务出现问题的时候，如何帮助用户快速的找到问题的症结。

设计一个能用的API容易，但设计一个全面周到的API，难！有服务精神的人明白，用户的赞许和微笑才是他们快乐的源泉，所以他们并不会止步于可用就好，而是追求卓越的服务质量。这种动力会引领他们不断的挑战自我，超越自我。如果你身边有这样的同事，不管是你和他一起开发API，还是使用他的API，祝贺你，你中奖了。

2018年6月更新 已离职，再见，Murex！

三年前，我谈了一次Murex面试。之后，陆陆续续一直有朋友打听Murex。这次结合我的经历和见闻，从学习氛围的角度，再谈一下Murex。

为什么谈学习氛围？除了技术团队之外，我还自愿加入了Murex Dev Branding团队。Branding团队的目的，是为了提升Murex品牌，吸引优秀的软件工程师。想要吸引优秀的程序员，必须先了解程序员们的需求。为此，我们做了大量的需求调研。结果显示，程序员们最重要的需求，是学习！

DevDailies

爱学习，但没时间？Daillies帮助你在繁忙的工作中，找到学习的时间。

我的同事Jonathan，在Devoxx讲了他的DevDaillies的经历，Les Dailies: une nouvelle façon agile d’apprendre en entreprise。大致的做法是，公司内部的一个同事，选择一个他感兴趣的话题，每天十分钟，直接在办公室里给大家传授知识。你只需要转动一下椅子，就可以享受到一个精心准备的知识点。目前，同事们分享了Dailly C++, Dailly Java, Dailly Functional Programming。

Java，C++社区

每个小组所处的环境不同，使用一种编程语言的方式就会不一样。实时金融数据小组，使用Java，注重性能的优化。服务框架小组，更看重Java的扩展性，比如依赖注入。在不同的小组，不同的程序员之间分享编程语言的不同特性，是Java，C++社区的任务。除了分享，如果你有问题，也可以像以上社区寻求帮助。

Conference JavaOne, CppConf, Devoxx

Murex的程序员，每年有机会参加各种各样的技术会议，远到三番的JavaOne，近到骑车十分钟Le Palais de Congress的Devoxx。我本人上一年九月份公费参加了JavaOne，上周刚结束了Devoxx。这些会议，可以帮助程序员在正常的工作中，抽出身来，呼吸一下新鲜空气，扩大视野。

TekTalk

不仅Murex内部之间的人，可以通过社区互相帮助，互相分享知识。我们还会时不时的邀请一些外面的热情人士给我们做演讲。上一次的精益创业的演讲就是在TekTalk的情境下进行的。下图是RedHat的朋友给我们介绍Vert.x。

Meetup

为了方便程序员们在自己的公司就能参加Meetup，Murex会时不时为Meetup提供场地。

培训

Murex目前处在转型的重要关头，如何处理技术负债，如何在老代码的基础上继续创新是一大挑战。为此Murex组织一系列的和Craftmanship相关的培训，其中最重头的就是Working Effectively with Legacy Code的作者Michael Feathers的到来。

CodingDojo

喜欢算法和数据结构吗？每周四的中午12点到14点，算法爱好者相聚CodingDojo，训练我们解决问题的能力。从LeetCode，到CodeJam，到Project Euler，作为程序员，擦亮你的枪杆子！

看这张图，拿披萨盒子当演算纸，厉害了，我的兄弟！

CodinGame/HashCode Hub

竞技编程爱好者，在Murex也能找到战友。同事Manwe在Devoxx分享了他的AI战斗秘籍，每逢CodinGame的比赛，Murex都会组织一个CodinHub。

结语

如果你也有学习的需求，却苦恼周围没有学习的氛围，那你需要怎么办？请仔细想一想。
最后，希望这篇文章能更生动地给大家展现一下Murex。

这次利用业余时间参加了CodinGame的Ghost In the Cell人工智能游戏比赛，下面记录一下比赛中所积累到的经验。一是希望下次能做的更好，二来希望能给没有参加过比赛但是有浓厚兴趣的朋友，起到个抛砖引玉的作用。

赛果

• 传奇者联盟
• 总排名: 59/3508
• 语言排名Scala: 2/50

游戏概述

比赛双方各拥有一个主基地和一定数量的兵力。除了主基地之外，地图上还有待征服的其他基地。每个基地都有一定的产能，一旦拥为己有，就可以生产新的兵力。征服一个基地，需要往基地上派遣足够的兵力，谁的兵力多谁胜。一旦占领基地之后，选手可以通过牺牲十个兵力来转化为基地的永久产能。此外，每个选手还拥有两个炸弹，可以投放到基地上，摧毁在目标基地上的兵力，并且阶段性暂停兵力生产。最后谁的兵力最多谁获胜。更多细则，请参考比赛主页。

策略篇

之前的比赛（比如Coder Strike Back, Great Escape)，可以利用优化算法（比如基因算法，Minimax算法）对整个游戏进行模拟，无须深入挖掘游戏策略，就可以找到非常高效的方案。

Ghost in the Cell这款游戏一大特点就是巨大的搜索空间（分支因子过大），导致我们无法通过全面的模拟来实现优化的解决方案。这种情况下，我们必须要利用人脑对问题深入分析，设计一个为这款游戏量身定做的策略。这种利用人脑分析引导程序搜索解决方案的方法，叫做启发式（heuristic）算法。启发式算法，不能保证最优的解决方案，但可以在相对短的时间内，找到符合一定条件的方案。

这种方法的效率非常依赖于人们对问题的理解，因此，选择了启发式算法，就要深挖游戏中的概念和规律。接下来是我为对游戏的理解。每次理解得到升级，我的排名都会直线上升。

部队机动性

一旦一个部队从基地上被派遣出去，我们便失去了对它的控制，直至它到达目的地。所以我们要限制在路上的部队，与其让它们长途跋涉，我们应该为它们找到中转基地。这样可以增加部队的机动性，如果在到达中途基地的时候，战况和预估的有差异，我们可以给它们下达新的命令，执行新的任务。

出乎意料的是，通过中转基地的路径，会比直达路径更快。就好像，某些中转基地之间有快车道一样。计算最优路径有现成的算法：Floyd Warshall algorithm。这里是我的scala implementation。

距离和产能的天然效应

即便我们可以在部队的数量上胜过对方，我们也未必能征服对方。假如基地A和基地B每轮产生等量的部队，那么基地A必须在起始兵力上拥有一定的优势，才能攻陷基地B。

举例来说，基地A和基地B，初始各有2只部队，并且每轮都生产2个新部队（产能为2），基地A和基地B相距四步。如果基地A在第一轮输送2个部队到基地B，当它们到达目的地时，基地B将坐拥2+4*2=10支部队。因此基地A的2只部队并不能撼动基地B。
基地A必须派遣至少2+4*2+1=11部队才能拿下基地B。因此，基地A的兵力优势必须达到4(路程)*2(产能)=8以上才能发起有效的进攻。因此远征难，没有十足把握，不必发动攻击，而是要利用现有的部队去做更有效的任务，比如扩大产能。

一旦理解了距离和产能的效应，我们可以计算每个基地的时间线。简单来说，就是可以通过计算基地的产能和发往基地的部队，算出基地在每个时间点的占有者和所持有的兵力。这个时间点是我进行攻防策略设计的最重要的根据。

具体来说，对每个基地我都会计算它的20轮后投入产出比，最终的兵力/所需投入的兵力。

炸弹的释放和躲避

炸弹可以摧毁对方的部队，拖延对方的产能。用好它要选择好地点和时机。炸一个没有部队没有产能的基地，没有任何效果。等到自己部队都快要被消灭殆尽的时候再释放炸弹起不了任何作用。因此好的策略，是利用炸弹阻止对方的扩张，为自己的扩张争取时间。

很多人的都选择在比赛一开始，就释放炸弹，这样炸弹会经历一段相对很长的过程才能到达目的地，这个时长增加的炸弹打击的不确定性。我所选择的方案，是在地图的中心点释放炸弹。这样我可以缩短从炸弹释放到炸弹爆炸的时长，进而降低不确定性。

选择中心点当做炮台还有一大优势。值得注意的是，炮弹不能像部队那样，可以利用中转基地缩短两点之间的距离。因此先攻占中间点在发送炸弹可以缩短炸弹爆炸的绝对总时长。

方法篇

在处理一些复杂问题的时候，我们不可能事先就制定一个完美解决方案，因为有很多概念、规律会隐藏的很深。通常，我们要通过实践去学习，边实践边发现。下面介绍一下处理复杂问题的一些方法。

千里之行，始于脚下

边实践边学习的精髓，就是要实践。千里之行，始于脚下，不要怕步子迈的小，一定要走出去。所以，不要多犹豫，开始写代码吧。

这也是我学习离散优化课程中老师大力推荐的方法。先从贪婪算法开始，有助于帮助更深刻的理解问题，发现可以优化的地方，也可以从心里上得到阶段性的成就感。接着再设计更加稳定可靠的优化算法，循序渐进的解决问题。

观察

观察能力，是非常重要的学习能力，通过观察，你可以找到内在的规律，就比如远征难的概念。CodinGame里，你可以观看排行榜上高手的比拼，从他们哪里可以观察到许多有用的策略。

放松

如果你感觉到阻塞，停滞不前了。一定要学会放松，去散步，打球，放空，好的想法说不定在你洗澡的时候就冒出来了。

实战篇

完美的计划，精妙的策略，不执行，都是纸上谈兵。选择一款好的编程语言，好的开发环境，会节省你开发的时间，进而给你更多时间去实践和学习。

Scala语言

Scala把指令时编程和函数式编程结合在了一起，并且对Immutablility有特别好的支持，基于篇幅的限制，我接下来打算专门写一篇文章，介绍面向函数式编程在人工智能对战游戏中的应用。

CodinGame

鉴于CodinGame平台的特点，只能提交一个源文件的限制，我开源了我的CodinGame工具：CodinGame Scala Kit。欢迎大家使用。

结语

这段难忘的比赛经历，让我学到了很多东西。细想起来，主要是我真真正正的投入了进去，这就是竞技编程的魅力。