OJ 总结(Depricated)
2015.01.04
题目大意就是一种更好的 Binary Search，在一个已经排好序的数组里面找到 target，返回 target 索引。如果找不到，那么就返回 target 应该插入的位置。
我觉得还是 Acclerated C++ 那本书给了我很多启示。Binary search 的搜索区间看作是一个左闭右开区间，每次迭代的过程中，不变的准则是：区间的右边是开区间。这样可以省去考虑中间点恰好是 target 的麻烦。这样做的好处除了省去中间点的考量外，也省略掉了尾端的考虑：在 C 语言中，整数类型向 0 取整，所以 4 是 end 的话，所有小于 4 的数与之相加除以 2 的结果都必然小于 4。
当然这样没考虑区间左端。有一种情况区间左端小于 target，这时候就简单地和等于的情况合并喽。
这道题没用迭代。用迭代还可以再缩短时间。
给定两个已排好序的数组，把它们 merge 成一个。不要再分配空间。
按照惯常的思路是从每个数组的开头开始一一比较然后插入，但这不是 Merge Sort。其实可以从每个数组尾端开始，从大到小插入。但是这样会不会污染原有数据呢？用数学方法证明一下即可。