线性表查找

衡量一个查找算法优劣的标准是查找过程中对关键字需要执行的平均比较次数，即平均查找长度（ASL）,将查找算法中的关键字的比较次数的数学期望值定义为平均查找长度。

ASL = ∑pici;(1 =< i <= n)

n 是问题规模，pi 是查找第 i 个数据元素的概率，ci 是查找第 i 个数据元素所需的关键字比较次数。

顺序查找

对顺序表可以进行顺序查找和二分查找，对链表只能进行顺序查找。最好情况下为 O(1),最坏和平均情况都为 O(n)。

二分查找

前提：顺序表是有序的。

非递归算法：

/**
 * 二分查找
 * @param a 查找的顺序表
 * @param key 查找的关键字
 * @return
 */
public static int binSearch(int a[], int key) {
    int n = a.length;
    int low = 0, high = n - 1, mid;
    while(low >= high){
        mid = (low + high) / 2;
        if (key == a[mid]) return mid;
        else if (key < a[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

复杂度：

二分查找的核心是对长度为 n 的数组进行分割。 while 循环中每循环一次二分，表长减为原来一般。假设 while 中执行的次数是 k 。则执行到第 K 次表长为 n/(2^k)。在查找过程中表长要大于等于1.则 k <= log2(n)。所以 T(n) = O(log2(n)。

分块查找

分块查找的基本思想是将原表分成若干块，各块内部不一定有序，但第 i 块内所有记录的关键字都小于第 i+1 块内所有记录的关键字。抽取各块中的最大关键字和起始位置建立索引表，索引是有序的。所以分块查找就是想用二分查找或顺序查找（索引表）待查节点在那一块，然后在块中进行顺序查找。实际上是两次查找过程，效率介于顺序查找和二分查找之间。

比较

查找算法	存储结构	优点	缺点	使用于
顺序查找	顺序、链表机构	算法简单对表的结构无要求	查找效率低	n 较小的表的查找以及查找较少但改动较多的表（链表）
二分查找	顺序	查找效率高	关键字必须有序且只能用顺序存储结构	特别适合一经建立就很少改动又频繁查找的线性表
分块查找	顺序、链表	在表中插入或删除记录时只需在该记录所属块内操作，因为块内记录的存放是随意的，插入删除比较容易	要增加辅助数组存储空间，并需要将初始表分块排序运算	适用于有分块特点记录的表