搜索对象是一个数据的集合（称为搜索表），除了执行搜索外，还可能执行其他操作，例如添加新元素，这样可能会改变搜索表的结构。因此，搜索表可以区分为静态搜索表（表的结构不发生改变）和动态搜索表两种情况。
常见的适用于静态搜索表的搜索方法有：顺序搜索、折半搜索、Fibonacci搜索等。
适用于动态搜索表的搜索方法有：二叉排序算法，平衡二叉搜索算法。
二叉排序树搜索
二叉排序树（Binary sort Tree,BST）又称为二叉查找（搜索）树（Binary Search Tree） 。其必须为二叉排序树或者为空树，或者满足如下性质的二叉树：
（1）若它的左子树非空，则左子树所有结点的值均小于根结点的值；
（2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
（3）左、右子树本身又各是一颗二叉排序树。
由BST性质可得：
1）二叉排序树中任一结点x，其左（右）子树中任一结点y（若存在）的关键字必小（大）于x的关键字。
2）二叉排序树，各结点关键字是唯一的。
实际运用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质（1）里的“小于”改为“大于等于”，或将BST性质（2）里的“大于”改为“小于等于”，甚至可同时修改这两个性质。
3）按中序遍历该树所得到的中序序列是一个递增有序序列。
二叉排序树的存储结构表示如下：
typedef int KeyType;//假定关键字类型为整数
typedef struct node {//结点类型
KeyType key;//关键字项
InfoType otherinfo;//其他数据域，InfoType视应用情况而定，下面不处理它
struct node *lchild,*rchild;//左右孩子指针
} BSTNode;
typedef BSTNode *BSTree;//BSTree是二叉排序树的类型
B-树
当查找文件较大，且存放在磁盘等直接存取设备中时，为了减少查找过程中对磁盘的读写次数，提高查找效率，基于直接存取设备的读写操作以“页”为单位的特征。1972年提出了一种称之为B-树的多路平衡查找树。它适合在磁盘等直接存取设备上组织动态的查找表。一颗m（m>=3）阶的B-树是满足如下性质的m叉树：
（1）每个节点至少包含下列数据域：（j,P0,K1,P1,k2,……，Ki,Pi）。其中：
j为关键字总数，
Ki（1<=i<=j）是关键字，关键字序列递增有序：K1<K2<……<Ki。
Pi（0<=i<=j）是孩子指针。对于叶节点，每个Pi为空指针。
注意：
实际运用中没结束空间，叶节点可省去指针域Pi，但必须在每个结点中增加一个标志域leaf，其值为真时表示叶节点，否则为内部结点。
在每个内部结点中，假设用keys(Pi)来表示子树Pi中的所有关键字，则有keys(P0)<K1<keys(P1)<K2<……<Ki<keys(Pi),即关键字是分界点，任一关键字Ki左边子树中的所有关键字均小于Ki，右边子树中的所有关键字均大于Ki。
（2）所有叶子是在同一层，叶子层数位树的高度h。
（3）每个非根结点中所包含的关键字个数j满足：m/2-1<=j<=m-1,m为阶数。
即每个非根结点至少应该有m/2-1个关键字，至多有m-1个关键字。因为每个内部结点的个数正好是关键字总数加1，故每个非根的内部结点至少有m/2棵子树，至多有m棵子树。
（4）若树非空，则根至少有1个关键字，故若根不是叶子，则它至少有2棵子树。根至多有m-1个关键字，故至多有m棵子树。
B-树的结点规模
B-树的算法执行时间主要是由读写磁盘的次数来决定的，每次读写尽可能多的信息可提高算法的执行速度。
B-树的结点规模一般是一个磁盘页，而结点中的所包含的关键字及其孩子的数目取决于磁盘页的大小。
注意：
1）对于磁盘上一颗较大B-树，通常每个结点拥有的孩子数目（即结点的度数）m为50至2000不等。
2）一颗度为m的B-树称为m阶B-树。
3）选取较大的结点度数可降低树的高度，以及减少查找任意关键字所需的磁盘访问次数。
B-树的存储结构
#define Max 1000 //结点中关键字的最大数目：Max=m-1，m是B-树的阶
#define Min 500 // 非根结点中关键字的最小数目：Min=m/2-1
typedef int KeyType;//KeyType应由用户定义
typedef struct node {//结点定义中省略了指向关键字代表的记录的指针
int keynum;//结点中当前拥有的关键字的个数，keynum<<Max
KeyType key[Max+1];//关键字向量为key[1……keynum]，key[0]不用
struct node *parent; //指向双亲结点
struct node *son[Max+1];//孩子指针向量为son[0……keynum]
}BTreeNode;
typedef BTreeNode *BTree;
广度优先搜索
搜索图常用方法有深度优先搜索和广度优先搜索两种。它们对无向图和有向图都适用。
广度优先搜索（BFS）类似于树按层次遍历的过程。广泛应用于求解问题的最短路径、最少步骤、最优方法等方面。
广度优先搜索遍历图的过程中以V为起始点，由近及远，依次访问和V右路径相通且路径长度为1,2……的顶点。
BFS(图g，顶点s)
{
队列Q；
for(顶点u in g.所有顶点) u.状态=未访问;
s.状态=准备访问;
s.访问深度=0;
Q.入队(s);
while( Q.非空() )
{
顶点u=Q.出队();
for(顶点v in u.所有邻接点)
{
if(v.状态==未访问)
{
v.状态=准备访问;
v.访问深度=v.访问深度+1;
v.前趋点=u;
Q.入队(v);
}
}
u.状态=已访问;
}
}
深度优先搜索
DFS类似于树的先根遍历，是树的先根遍历的推广。常用于游戏软件开发中。深度优先搜索的核心思想是在搜索到尽头时，用栈记住下一步的走向。
DFS(图g,顶点s)
{
s.状态=正在访问;
for(顶点v in s.所有邻接点)
{
if(s.状态 == 未访问)
DFS(g,v);
}
s.状态=已访问;
}
在遍历图的时候，对图中每个顶点至多调用一次深度优先搜索，遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的数据结构。当用邻接矩阵存储图时，查找一个顶点的邻接点所需时间为O(n)(n表示图中顶点数目)，则总的时间复杂度为T(n)=O(n^2).
---------------------------------------------------------------------------------
参考文献《算法分析与设计》 （C++描述） 清华大学出版社 石志国