查找表是由同一类型的数据元素构成的集合。例如电话号码簿和字典都可以看作是一张查找表。   在查找表中只做查找操作，而不改动表中数据元素，称此类查找表为静态查找表；反之，在查找表中做查找操作的同时进行插入数据或者删除数据的操作，称此类表为动态查找表。

  顺序查找的查找过程为：从表中的最后一个数据元素开始，逐个同记录的关键字做比较，如果匹配成功，则查找成功；反之，如果直到表中第一个关键字查找完也没有成功匹配，则查找失败 同时，在程序中初始化创建查找表时，由于是顺序存储，所以将所有的数据元素存储在数组中，但是把第一个位置留给了用户用于查找的关键字。例如，在顺序表{1,2,3,4,5,6}中查找数据元素值为 7 的元素，则添加后的顺序表为：

            图1   顺序表的一端添加用户用于搜索的关键字，称作“监视哨”。   图 1 中监视哨的位置也可放在数据元素 6 的后面（这种情况下，整个查找的顺序应有逆向查找改为顺序查找）。   放置好监视哨之后，顺序表遍历从没有监视哨的一端依次进行，如果查找表中有用户需要的数据，则程序输出该位置；反之，程序会运行至监视哨，此时匹配成功，程序停止运行，但是结果是查找失败。 代码实现：

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

  折半查找，也称二分查找，在某些情况下相比于顺序查找，使用折半查找算法的效率更高。但是该算法的使用的前提是静态查找表中的数据必须是有序的。   例如，在{5,21,13,19,37,75,56,64,88 ,80,92}这个查找表使用折半查找算法查找数据之前，需要首先对该表中的数据按照所查的关键字进行排序：{5,13,19,21,37,56,64,75,80,88,92}。   在折半查找之前对查找表按照所查的关键字进行排序的意思是：若查找表中存储的数据元素含有多个关键字时，使用哪种关键字做折半查找，就需要提前以该关键字对所有数据进行排序。

  对静态查找表{5,13,19,21,37,56,64,75,80,88,92}采用折半查找算法查找关键字为 21 的过程为：

              图2 后一个关键字，指针 mid 指向处于 low 和 high 指针中间位置的关键字。在查找的过程中每次都同 mid 指向的关键字进行比较，由于整个表中的数据是有序的，因此在比较之后就可以知道要查找的关键字的大致位置。   例如在查找关键字 21 时，首先同 56 作比较，由于21 < 56，而且这个查找表是按照升序进行排序的，所以可以判定如果静态查找表中有 21 这个关键字，就一定存在于 low 和 mid 指向的区域中间。   因此，再次遍历时需要更新 high 指针和 mid 指针的位置，令 high 指针移动到 mid 指针的左侧一个位置上，同时令 mid 重新指向 low 指针和 high 指针的中间位置。如图3所示：

              图3   同样，用 21 同 mid 指针指向的 19 作比较，19 < 21，所以可以判定 21 如果存在，肯定处于 mid 和 high 指向的区域中。所以令 low 指向 mid 右侧一个位置上，同时更新 mid 的位置。

              图4   当第三次做判断时，发现 mid 就是关键字 21 ，查找结束。   注意：在做查找的过程中，如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间，即求得 mid 的位置不是整数，需要统一做取整操作。   折半查找的实现代码：

  动态查找表中做查找操作时，若查找成功可以对其进行删除；如果查找失败，即表中无该关键字，可以将该关键字插入到表中。   动态查找表的表示方式有多种，本节介绍一种使用树结构表示动态查找表的实现方法——二叉排序树（又称为“二叉查找树”）。

  二叉排序树要么是空二叉树，要么具有如下特点：

  例如，图 5 就是一个二叉排序树：

              图5

  二叉排序树中查找某关键字时，查找过程类似于次优二叉树，在二叉排序树不为空树的前提下，首先将被查找值同树的根结点进行比较，会有 3 种不同的结果：

  二叉排序树本身是动态查找表的一种表示形式，有时会在查找过程中插入或者删除表中元素，当因为查找失败而需要插入数据元素时，该数据元素的插入位置一定位于二叉排序树的叶子结点，并且一定是查找失败时访问的最后一个结点的左孩子或者右孩子。   例如，在图 1 的二叉排序树中做查找关键字 1 的操作，当查找到关键字 3 所在的叶子结点时，判断出表中没有该关键字，此时关键字 1 的插入位置为关键字 3 的左孩子。   所以，二叉排序树表示动态查找表做插入操作，只需要稍微更改一下上面的代码就可以实现，具体实现代码为：

  通过使用二叉排序树对动态查找表做查找和插入的操作，同时在中序遍历二叉排序树时，可以得到有关所有关键字的一个有序的序列。   例如，假设原二叉排序树为空树，在对动态查找表 {3，5，7，2，1} 做查找以及插入操作时，可以构建出一个含有表中所有关键字的二叉排序树，过程如图6 所示:

              图6   通过不断的查找和插入操作，最终构建的二叉排序树如图 6（5） 所示。当使用中序遍历算法遍历二叉排序树时，得到的序列为：1 2 3 5 7 ，为有序序列。 一个无序序列可以通过构建一棵二叉排序树，从而变成一个有序序列。

  在查找过程中，如果在使用二叉排序树表示的动态查找表中删除某个数据元素时，需要在成功删除该结点的同时，依旧使这棵树为二叉排序树。   假设要删除的为结点 p，则对于二叉排序树来说，需要根据结点 p 所在不同的位置作不同的操作，有以下 3 种可能：

              图7   (2)用结点 p 的直接前驱（或直接后继）来代替结点 p，同时在二叉排序树中对其直接前驱（或直接后继）做删除操作。如图 8 为使用直接前驱代替结点 p：