算法的泛化问题，这些坑你可能都经历过！|周立功教你学软件设计

由于findValue函数的返回值begin是一个指针，因此该函数是一个返回指针的函数，即指针函数。这个函数在"前闭后开"范围[begin, end)内（包含了begin迭代器的当前元素，而到end迭代器的前一个元素为止）查找value，并返回一个指针，指向它所找到的第一个符合条件的元素，如果没有找到就返回end。这里之所以用"!="，而不是用"<"判断是否到达数组的尾部，因为这样处理更精确。findValue()函数的使用方式如下：

const int arraySize = 7; 

int array[arraySize] = {0, 1, 2, 3, 4, 5, 6}; 

int *end = array + arraySize;

 

int *ip = findValue(array, end, 4);

if(ip == end) 

       return false; 

else 

       return true; 

 

当然，findValue()函数也可以方便地用于查找array的子范围：

int *ip = findValue(array + 2, array + 5, 3); 

if(ip == end) 

       return false; 

else

       return ture; 

 

由此可见，findValue()函数中并无任何操作是针对特定的整数array的，即只要将操作对象的类型加以抽象化，且将操作对象的表示法和范围目标的移动行为抽象化，则整个算法就可以工作在同一个抽象层面上了。通常将整个算法的过程称为算法的泛型化，简称泛化。泛化的目的旨在使用同一个findValue()函数处理各种数据结构，通过抽象创建可重用代码。

 

如果一个序列是有序的，则不需要用finValue()从开始位置查找，可以使用标准C提供的bsearch()二分查找算法。对于一个更长的序列，二分查找也比findValue()线性查找法的速度更快。即使序列中只有10个元素，也足以体现二分查找的比较优势。对于一个有1000个元素的序列，最多需要进行10次比较，其查找的速度要快200倍。

 

显然，求数组中元素的最大值，其最好的方法是通过传递2个指针指定元素范围。一个指针标识数组的开头，另一个指针标识数组的尾部。比如：

int iMax(const int *begin, const int *end);

 

显然，如果只是传递指针，数据就有被修改的可能。如果不希望数据被修改，就要传递指向整数常量的指针。使用for循环的示例如下：

for(ptr = begin; ptr != end; ptr++)

       total = total +*ptr; 

 

将ptr设置为待处理的第一个元素（begin指向的元素）的指针，并将*ptr（元素的值）加入到total中。然后循环通过递增操作来更新ptr，使之指向下一个元素。只要ptr不等于end，这一过程将继续下去。当ptr等于end时，它将指向范围中的最后一个元素后面的位置，此时循环结束。其次，请注意不同的函数调用是如何指定数组中不同的范围的。比如：

int array[] = {39, 33, 18, 64, 73, 30, 49, 51, 81}; 

int n = sizeof(array) / sizeof(array[0]); 

int *past = array + n;

 

int max = iMax(array, array + n); 

int max = iMax(array, array + 3); 

int max = iMax(array +3, array + 8); 

 

指针array+n指向最后一个元素后面的一个位置（数组只有n个元素，最后一个元素的地址为array+n-1），因此范围[array，array+n]指定的是整个数组。同样array，array+3指定了前3个元素，依此类推。注意，根据指针减法规则，表达式end–begin是一个整数值，等于数组的元素个数。