转自：http://hatewx.blog.163.com/blog/static/3671472520124176354829/
今天复习一下几种查找算法和其时间和空间复杂度：
一、静态查找表
1.顺序查找：
原理是让关键字依次与队列中的数从第一个开始逐个比较，直到找出与给定关键字相同为止。
用Java实现如下：
如果X位于序列中，假定在i处，x=Si，且i<n，则循环将迭代i次，在这种情况下，运算时间正比于I，即为O(n)（因为i<n）。
假如X不在序列中，循环将n次，使得运行时间正比于n，也就是O(n)。
2.二分法查找（折半查找法）
折半查找(Binary Search)是查找有序列平均分成两半，如划分点元素不是我们所要查找的元素。则将在有可能查找元素的子序列中查找，重复上述过程，直到找到或找遍为止。
优点：比较次数少，查找速度快，平均性能好。
缺点：要求其为有序表。必须采用顺序存储结构。
用Java实现如下：
在每次迭代中，当Si=X时，将返回索引值i。否则，子序列长度将减少百分之五十多，序列有限个元素，必将在有限步内终止。因此当算法终止于循环中部，将返回索引值i。或当终止于循环循环末尾，返回-1。（h<l），也即当前子序列为空序列。Si不在序列当中。
循环迭代交数最多为n能连续被2除（取整）的次数加1，也即以n以2为底的对数取整加1 ，因此，算法的时间复杂度为O(lg2n)。
3.分块查找（索引顺序查找）
它是顺序查的的一种改进方法。在此查找法中，除本身外，尚需建立一个"索引表"。索引表里有m个记录，每个索引n个元素，m*n等于数组的长度。其中包括两项内容：关键字（其值为该子表最大关键字）和指针（指示表第一个记录在表中的位置）
过程分两步进行：1.先用二分法查找索引表，确定要找的记录在哪一块; 2.然后再在相应块用顺序查找找到目标记录。分块查找又称为索引顺序查找。
Java代码实在如下：
使用了二分查找法和顺序查找法，所以其时间复杂度应为二者之合。即：O(log(2m))+O(n)=O(log(2m)+n)=O(log(2m)+length/m)