2015.01.04

Simple Binary Search

题目大意就是一种更好的 Binary Search,在一个已经排好序的数组里面找到 target,返回 target 索引。如果找不到,那么就返回 target 应该插入的位置。

我觉得还是 Acclerated C++ 那本书给了我很多启示。Binary search 的搜索区间看作是一个左闭右开区间,每次迭代的过程中,不变的准则是:区间的右边是开区间。这样可以省去考虑中间点恰好是 target 的麻烦。这样做的好处除了省去中间点的考量外,也省略掉了尾端的考虑:在 C 语言中,整数类型向 0 取整,所以 4 是 end 的话,所有小于 4 的数与之相加除以 2 的结果都必然小于 4。

当然这样没考虑区间左端。有一种情况区间左端小于 target,这时候就简单地和等于的情况合并喽。

这道题没用迭代。用迭代还可以再缩短时间。

Merge Sorted Array

给定两个已排好序的数组,把它们 merge 成一个。不要再分配空间。

按照惯常的思路是从每个数组的开头开始一一比较然后插入,但这不是 Merge Sort。其实可以从每个数组尾端开始,从大到小插入。但是这样会不会污染原有数据呢?用数学方法证明一下即可。


留言