lowerBound和upperBound

话说lowerBound和upperBound真是一对神奇的函数。如果说一个人把quick sort写了十遍，当他第十一遍开始写quick sort的时候，那绝对叫一个轻车熟路啊，绝对是soso的。

但是lowerBound和upperBound这对函数，我去年刷leetcode的时候写了n遍，简直到了闭眼都能墨写的程度。这两天又刷leetcode，拿起来竟然又一脸楞比。

于是乎我打算“一劳永逸”的解决这个问题 —- 记下来，哈哈哈

lowerBound/upperBound 的含义

lowerBound/upperBound的含义是：在一个排序好的数组里找一个位置插入，使得插入后数组仍然是排序好的。

lowerBound/upperBound的区别在于，lowerBound找的是最小的下标，upperBound找的是最大的下标。

111, 222, 333
   ^    ^
   |    可以把222插入到这里，这里是upperBound
   也可以把222插入到这里，这里是lowerBound

实现

lowerBound/upperBound的实现异常的简洁。因为完美实现非常的精巧，但是里面的边界控制实在是非常的绕人，所以写一次忘一次。

function lowerBound(A, t) {
    var l = 0, r = A.length;  // 初始化左右边界，注意这里r指向最后一个元素右侧的位置
    
    while (l !== r) {                    // 这里是判断不相等，而不是距离>1
        var m = Math.floor((l + r) / 2); // 使用floor正好避开了越界
        if (t > A[m])                    // 改为>=即是upperBound
            l = m + 1;                   // 这里是m+1而不是m
        else
            r = m;
    }
    
    return l;
}

总共才11行，但不得不说，每一行都有雷。这叫一个心累啊。

这个版本基本上可以成为范式版本了，因为改动任何一个细节都会多出n行废代码。

无论是stl的实现，还是xxx的实现，全部是这个版本。只不过表述细节不一样。

把代码中唯一的那个if语句中的 > 改为 >= 就可以获得upperBound函数。

和binarySearch的关系

binarySearch可以简单的用lowerBound或upperBound实现。但是C++里提供了独立的函数。用binarySearch函数的好处是，如果有很多的重复元素，碰到一个就可以提前中止。但是说实话这个价值真的不大，优化的价值非常的有限，反而binarySearch的实现代码里每一次有两个if语句，谁跑的快还真不好说。

我个人不太喜欢binarySearch函数，而总是使用lowerBound/upperBound。