查找

查找（ Search ）是查询、修改、插入、删除等操作的基础，是数据结构中研究的重要运算。所谓查找即是按照某一个关键字值，在数据结构中找出元素的关键字值与被查元素的关键字值满足查找条件的结点。若找到，称查找成功；否则（找不到）称查找失败。

关键字可以是数据元素中某个数据项，也可以是数据元素中的数据项组，用它可以标识一个数据元素。能唯一确定一个数据元素的关键字称为主关键字；不能唯一确定一个数据元素的关键字称为次关键字。

查找算法分为线性表的查找、树的查找、散列查找和索引查找4 种。

顺序查找

顺序查找（ Sequential Search ）又称顺序搜索。它从线性表的第一个元素开始，依次将线性表中元素的关键字值与被查元素的关键字值进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。

二分法查找

二分法查找（ Binary Search ）只适用于顺序存储的有序表。有序表是指线性表中的元素按关键值从小到大（或从大到小）排序。二分法查找的过程如下：首先取中间元素作为比较对象，若给定值与中间元素的关键字值相等，则查找成功；若给定值小于中间元素的关键字值，则在中间元素的上半区继续按同样的方法查找；若给定值大于中间元素的关键字值，则在中间元素的下半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。

显然，二分查找的效率要比顺序查找高得多。对于长度为 n 的有序线性表，在最坏情况下，二分查找只需要比较 log2n 次。