基础查找算法
——.NET数据结构与算法系列之三
追忆，2013年11月19日
前言
数据查找是基础的计算机编程工作，而且人们对它的研究已经很多年了。在本部分只会看到查找问题的一个内容，即根据给定的数值在一个列表（数组）中进行查找。
有两种对列表内数据进行查找的方法：顺序查找和二驻查找。当数据项在列表内随机排列的时候可以使用顺序查找，而当数据项在列表内有序排列的时候则会用到二叉查找。
1.顺序查找算法
最突出的查找类型就是从记录集的开始处顺次遍历每条记录，直到找到所需要的记录或者是到达数据集的末尾。这就是所谓的顺序查找。
顺序查找（也称为线性查找）是非常容易实现的。从数组的起始处开始，把每个访问到的数组元素依次和所要查找的数值进行比较。如果找到匹配的数据项，就结束查找操作。如果遍历到数组的末尾仍然没有产生匹配，那么就说明此值不在数组内。
下面是一个执行顺序查找操作的函数：
//顺序查找 是否存在
public static bool SeqSearch(int[] arr, int sValue)
{
for (int index = 0; index < arr.Length; index++)
{
if (arr[index] == sValue)
//在这里也可以返回sValue在数组arr中的位置 return index;
return true;
}
return false;
}
很简单的基础查找。
1.1查找最小值和最大值
人们经常要求计算机程序从数组（或者其它数据结构）里查找最小值和最大值。在一个有序的数组中，查找最小值和最大值是很容易的工作。但是，在一个无序的数组中，这有个小小的挑战。
下面从如何找到数组的最小值开始：先上算法：
1、 把数组的第一个元素作为最小值赋给个变量。
2、 开始循环遍历数组，并且把每一个后继数组元素与最小值变量进行比较。
3、 如果当前访问到的数组元素小于最小值，就把此元素赋值给最小值变量。
4、 继续上述操作直到访问到最后一个数组元素为止。
5、 最小值就是存储在变量内的数值了。
//查找最小值
public static int FindMin(int[] arr)
{
int min = arr[0];
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
}
return min;
}
注意数组查找是从第1个元素开始的，而不是从第0个元素的位置开始。第0个元素的位置在循环开始前会获得最小值，因此开始进行比较操作是在第1个元素的位置上。
在数组内查找最大值的算法和查找最小值的类似。先把数组的首元素赋值给一个保存最大值的变量。接着循环遍历数组，把每个数组元素与存储在变量内的数值进行比较。如果访问到的数值大于当前，就进行替换。代码如下：
//查找最大值
static int FindMax(int[] arr)
{
int max = arr[0];
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] > max)
max = arr[i];
}
return max;
}
1.2自组织数据加快顺序查找速度
当要查找的数据元素就在数据集合的开始处时就会产生最快速的成功查找。通过找到数据项后把它移到到数据集合开始处的方法可以确保成功定位数据项。
这种策略的含义就是通过把频繁查找的数据项放在数据集合开始处的方法来最小化查找的次数。最终的结果就是所有最频繁查找的数据项都会被放置在数据集合的开始部分。这是自组织的一个实例，这是因为数据集合不是在程序运行之前由程序员组织的，而是在程序运行期间由程序自身组织的。
既然要查找的数据大概会遵循“80-20”规则，这使得允许数据进行组织变得有意义了。其中“80-20”原则意味着在数据集合上80%的查找操作都是为了查找数据集合内20%的数据。自组织将最终把20%的数据放在数据集合的开始部分，这样顺序查找就可以快速地找到它们了。
像这样的概率分布被称为是帕累托分布，它是以19世纪后期通过研究收入和财富的扩散而发现这类概率分布的科学家Vifredo Pareto的名字命名的。
在这里很容易地修改SeqSerch方法来包含自组织。下面是此方法的第一部分修正：
//顺序查找 改进方法
public static bool SeqSearchImprove(int[] arr, int sValue)
{
for (int i = 0; i < arr.Length - 1; i++)
{
if (arr[i] == sValue)
{
int tmp = i - 1;
Swap(arr, ref i, ref tmp);
return true;
}
}
return false;
}
如果查找成功，那么会利用交换函数把找到的数据项与元素在数组的第一个位置上进行交换，显示如下所示：
//交换值
private static void Swap(int[] arr, ref int item1, ref int item2)
{
int temp = arr[item1];
arr[item1] = arr[item2];
arr[item2] = temp;
}
正如上述已经修改过的一样，用SeqSearch方法的问题就是在多次查找过种中会相当多次地频繁访问到的数据项移来移去。而这里希望把移动到数据集合开始处的数据项保留下来，并且当对集合后部一个后续数据项成功定位的时候也不用把它保留的数据项移回去。
现在有两种方法可以实现这个目标。第一种方法是交换那些找到的且位置远离数据集合开始处的数据项。这样只需要确定到底在数据集合内多么靠后的元素才需要交换。再交遵循“80-20”规则，这里可以定义一条原则，那就是只有当数据项的位置位于数据20%数据项之外的时候才可以把它重新定位到数据集合的开始部分。下面是经过第一次改写的代码：
public static int SeqSearchImproveO(int[] arr, int sValue)
{
for (int index = 0; index < arr.Length - 1; index++)
{
if (arr[index] == sValue && index > (arr.Length * 0.2))
{
Swap(arr, index, index - 1);
return index;
}
else
{
if (arr[index] == sValue)
return index;
}
}
return -1;
}
这里的if-else语句是短路的。是因为如果无法在数据集合内找到数据项，那么就没有理由检测到该项在数据集合内的索引位置了。
另外一种方法就是重写SeqSearch方法，从而使得此方法可以把找到的数据项与数据集合内此项之前的元素进行交换。采用这种方法类似于数据排序时采用的冒泡排序方法，也就是说最终会把最频繁访问到的数据项按照它们的方式到达数据集合的前端。同时，这种方法也保证了不会把已经在数据集前面的数据项移到回到后边去。
不论基于何种原因，上述两种方法都会在需要保持数据集合无序状态的时候帮助进行查找。接下来我们讨论一种只处理有序数据但比任何已提到的顺序查找算法都要更高效的查找算法，即二叉查找。
2.二叉查找算法
当要查找的记录从头到尾都是有序排列的时候，为找到数值可以执行一种比顺序查找更加有效的查找。这种查找被称为二叉查找。
为了理解二叉查找的工作原理，假设你正在试图猜测由朋友选定的一个在1至100之间的数字。对于每次你所做的猜测，朋友都会告诉你是猜对了，还是猜大了，或是猜小了。最好的策略是第一次猜50。如果猜大了，那么就应该再猜25。如果50猜小了，则应该再猜75。在每次猜测的时候，你都应该根据调整的数的较小或较大范围（这依赖于你猜测的数是偏大还是偏小）选择一个新的中间点作为下次要猜测的数。只要遵循这个策略，你最终一定会猜出正确的数。如我们猜数82的策略过程如下：
1、 游戏猜测的数字是82.
2、 第1次猜50。答案太小了。
3、 第2次猜75。答案太小了。
4、 第3次猜88。答案太大了。
5、 第4次猜81。答案太小了。
6、 第5次猜84。答案太大了。
7、 中间点是82.5，这近似于82。
8、 第6次猜测82，答案正确。
这里可以把这种策略作为一种算法来实现，即二叉查找算法。为了使用这种算法，首先需要把数据按顺序（最好是升序方式）存储到数组内（当然，其它数据结构也可行）。
算法的第一步就是设置查找的上界和下界。在查找的开始，这就意味着是数组的上限和下限。然后通过把上限和下限相加除以2的操作就可以计算出数组的中间点。接着把存储在中间点上的数组元素与要查找的数值进行比较。
1、如果两者相同，那么就表示找到了该数值，同时查找算法也就此结束。
2、如果要查找的数值小于中间点的值，那么就通过从这中间点减去一的操作计算出新的上限。
3、否则，若是要查找的数值大于中间点的值，那么就把中间点加一求出新的下限。
此算法反复执行直到下限和上限相等时终止，这也就意味着已经对数组全部查找完了。如果发生这种情况，那么就返回-1，这表示数组中不存在要查找的数值。
实现算法如下：
//二叉查找测试
public static void BinSearchTest()
{
CArray theArray = new CArray(10);
theArray.Create(10);
theArray.BubbleSort();
theArray.DisplayElements();
while (true)
{
Console.WriteLine(" Enter a number to search for");
try
{
int num = Convert.ToInt32(Console.ReadLine());
int position = theArray.BinSearch(num);
if (position > -1)
{
Console.WriteLine("Founded");
}
else
{
Console.WriteLine("Not Founded");
}
}
catch
{
Console.WriteLine("非法字符");
}
}
}
不论基于何种原因，上述两种方法都会在需要保持数据集合无序状态的时候帮助进行查找。接下来我们讨论一种只处理有序数据但比任何已提到的顺序查找算法都要更高效的查找算法，即二叉查找。
3递归.二叉查找算法
尽管在上面讲述的二叉查找算法是正确的，但它其实浊解决问题的正常方案。二叉查找算法实际是一种递归算法。这是因为此算法会不断地划分数组直到找到所要的数据项（或者是查找完全部数组）才会终止，而每次的划分都是表示成一个比原有问题规模更小的同类问题。这种分析问题的方式使得人们终于发现了执行二叉查找的递归算法。
为了使递归二叉查找算法可以执行，这里需要对代码进行一些改动。下面先来看一下代码，然后再讨论已经修改的内容：
//递归二叉查找算法
public int RBinSearch(int value, int lower, int upper)
{
if (lower > upper)
return -1;
else
{
int mid;
mid = (int)(upper + lower) / 2;
if (value<arr[mid])
{
return RBinSearch(value, lower, mid - 1);
}
else if(value==arr[mid])
{
return mid;
}
else
{
return RBinSearch(value, mid + 1, upper);
}
}
}
同迭代算法相比，递归二叉查找算法的主要问题是它的效率。当用这两种算法对含有1000个元素的数组进行排序的时候，递归算法始终比迭代算法慢了10倍。
当然，选择递归算法常常是由于效率以外的其它原因，但是应该记住在任何实现递归算法的时候还应该寻找一种迭代的解决方案，这样全球比较两种算法的效率。
小结
查找数据集合内的数值是一种随处可见的计算机操作。最简单的查找数据集合的方法是从数据集合的头部开始查找数据项，直到查找到该数据项或者执行到数据集合的末尾才结束。这种查找方法最好用在数据集合相对较小且无序的时候。
如果数据集合是有序排列的，那么二叉查找算法会是一较好的选择。二叉查找会持续划分数据集合直到找到所要查找的数据项为止。
相对从理论上来讲，二叉查找要比顺序查找要快些，有兴趣的朋友可以试下。最近事情有点多JJJ
源程序下载：DataStructAndAlgorithm.zip
参考书箱：<<数据结构与算法>>