3.1　基于遍历的选择与查找

选择是与元素之间的序关系紧密相关的一个问题。首先对于一个包含n个各不相同元素的全序集，定义元素的阶(rank)的概念：定义一个元素的阶为k(1≤k≤n)，如果有k－1个元素比它小，n－k个元素比它大。阶为k的元素即为排名第k小的元素。基于阶的概念，我们可以定义选择问题。
定义3.1（选择问题）
●输入：n个各不相同的元素组成的全序集，参数k (1≤k≤n)。
●输出：阶为k的元素。
选择问题的一个简单而常用的特例是选择最大(阶为n)/最小(阶为1)的元素。为此只需要简单遍历所有输入的元素，记录遇到的最大/最小值的元素即可。这一方法的实现如算法3所示。选择问题的另一个常用的特例是选择中位数，即阶为n2的元素。使用上述反复遍历选择最值的方法，选择中位数的代价为O(n2)。对于一般的选择阶为k的元素的问题，我们可以通过反复选出最小的元素，重复k次直至选出第k小的元素。这一基于反复遍历方法的代价为O(kn)，这一代价在最坏情况下同样是O(n2)。在第8章，我们将讨论如何将选择的时间改进到线性时间。算法3：SELECT-MAX(A［1..n］)
1　index-of-max∶=－1;
2　current-max∶=－∞;
3　for i∶=1 to n do
4　if A［i］>current-max then
5　current-max∶=A［i］;
6　index-of-max∶=i;7　return index-of-max;查找问题要求从一堆键值中找出指定的值。
定义3.2（查找问题）
●输入：n个键值{k1,k2,…,kn}，键值key。
●输出：是否有某个键值ki=key(1≤i≤n)。
假设待查找的n个键值存储在一个数组中。如果未对键值作任何特殊的组织，则只能通过遍历整个线性表来查找指定的值。其实现如1.3节的算法2所示。要提高查找的效率，本质是对需要查找的数据作某种组织，并利用组织后的数据的特性，降低查找的代价。以基于遍历的查找为基础，我们将在第9章讨论更高效的数据组织方法与相应的查找算法。