1、折半查找、顺序查找、分块查找，平均查找长度的比较：

折半查找最小。分快查找，是将顺序表分为若干块，块内元素顺序任意，块间有序，即前一块中的最大值小于后一块中的最小值。并且有一张索引表，每一项存放每一块的最大值和指向该块第一个元素的指针。索引表有序，块内无序。所以，块间查找用二分查找，块内用顺序查找，效率介于顺序和二分之间。

2、链式存储的有序数据不能使用折半查找，因为无法直接访问折半时一半的位置处的元素。

3、一趟快速排序意思是：寻找一个支点，将该序列位置整个调整一边，

注意：支点不一定是左边第一个数，可以任意选的。

4、KMP算法下，长为n的字符串中匹配长度为m的子串的复杂度为

最好情况：每趟匹配不成功都是在第一个字符，即每趟都只需匹配一次就知道该趟是否匹配。O(m+n)

最坏情况：每趟匹配不成功都是在最后一个字符。时间复杂度O(m*n)。

5、hadoop 有单机版，伪分布一个节点，分布式。