1. 基本概念
查找的定义：给定一个值K，在含有n个记录的表中找出关键字等于K的记录。若找到，则查找成功，返回该记录的信息或者该记录在表中的位置；否则查找失败，返回相关的指示信息。
采用何种方法进行查找相关因素如下：
- 使用哪种数据结构来表示查找表，即查找表中的记录是按照何种方式组织的。
- 查找表中关键字的次序，即对无序集合查找还是对有序集合查找。
2. 基于线性表的查找
2.1 顺序查找
(1)思想：逐个比较，直到找到或者查找失败。
(2)时间复杂度：T(n) = O(n)。
(3)空间复杂度：S(n) = O(n)。
(4)程序：
public static int SeqSearch(int[] arr, int key){
for(int i = 0; i < arr.length; i++){//遍历数组
if(arr[i] == key)
return i; //查找成功，范围在数组中的索引
}
return -1; //查找失败，返回-1
}2.2 折半查找
(1)思想：又称二分查找，对于已经按照一定顺序排列好的列表，每次都用关键字和中间的元素对比，然后判断是在前部分还是后部分还是就是中间的元素，然后继续用关键字和中间的元素对比。
(2)时间复杂度：T(n) = O(log2n)。
(3)空间复杂度：S(n) = O(log2n)。
(4)程序：
public static int BSearch(int[] arr, int key){
int low = 0;
int high = arr.length-1;
int mid;
while(low <= high){
mid = (low + high) / 2; //获取当前数组的中间位置
if(arr[mid] == key){ //找到元素后，返回它所在位置索引
return mid;
}else if(arr[mid] < key){ //说明在arr[mid+1,...high]中查找
low = mid + 1;
}else{ //说明在arr[low,...mid-1]找查找
high = mid - 1;
}
}
return -1; //查找失败，返回-1.
}2.3 分块查找
(1)思想：分块查找把线性表分成若干块，每一块中的元素存储顺序是任意的，但是块与块之间必须按照关键字大小有序排序的，即前一块中的最大关键字要小于后一块中的最下关键字。对顺序表进行分块查找需要额外建立一个索引表，索引表中的每一项对应线性表中的一块，每一个索引项都有键值分量和链值分量组成，键值分量存放对应块的最大关键字，链值分量存放指向本块第一个元素和最后一个元素的指针（这里的指针可以是存放线性表数组中的元素下标或者地址，或者任何可以帮助找到这个元素的信心），显然索引表中的所有索引项都是按照其关键字递增顺序排序的。所以可以使用折半查找或者顺序查找确定关键字所在的子块位置。进入子块后，使用顺序查找查找。
(2)时间复杂度：T(n) = O(√n)
(3)空间复杂度：
(4)程序：（略）
3. 基于树的查找
3.1 二叉排序树
(1)思想：二叉排序树：①若它的左子树非空，则左子树上所有节点的值均小于它的根节点的值；②若它的右子树非空，则右子树上所有结点的值均大于（或大于等于）它的根节点的值；③它的左、右子树也分别为二叉排序树。查找的时候，中序遍历二叉树，得到一个递增有序序列。查找思路类似于折半查找。
(2)时间复杂度：插入一个节点算法的O(㏒n)，插入n个的总复杂度为O(n㏒n)。
(3)空间复杂度：
(4)程序：
BSTree SearchBST(BSTree bst, KeyType key)//递归算法
{
If(!bst)
return NULL;
else if(bst->key == key)
return bst;
else if(bst->key > key)
return SearchBST(bst->lchild, key);
else
return SearchBST(bst->rchild, key);
}
BSTree SearchBST(BSTree bst, KeyType key)//非递归算法
{
BSTree q;
q = bst;
while(q)
{
If(q->key == key)
return q;
else if(q->key > key)
q = q->lchild;
else
q = q->rchild;
}
return NULL;
}