数据结构与算法系列（3）基础查找算法

数据结构与算法系列（3）基础查找算法2014-04-26 博客园追忆前言

数据查找是基础的计算机编程工作，而且人们对它的研究已经很多年了。在本部分只会看到查找问题的一个内容，即根据给定的数值在一个列表（数组）中进行查找。

有两种对列表内数据进行查找的方法：顺序查找和二驻查找。当数据项在列表内随机排列的时候可以使用顺序查找，而当数据项在列表内有序排列的时候则会用到二叉查找。

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查找最小值和最大值

人们经常要求计算机程序从数组（或者其它数据结构）里查找最小值和最大值。在一个有序的数组中，查找最小值和最大值是很容易的工作。但是，在一个无序的数组中，这有个小小的挑战。

下面从如何找到数组的最小值开始：先上算法：

2、开始循环遍历数组，并且把每一个后继数组元素与最小值变量进行比较。

4、继续上述操作直到访问到最后一个数组元素为止。

1、游戏猜测的数字是82.

3、第2次猜75。答案太小了。

5、第4次猜81。答案太小了。

7、中间点是82.5，这近似于82。

<p CxSpLast" style="margin: 0cm 0cm 0pt 60pt;line-height: 17pt;;-ms-word -break: normal">8、第6次猜测82，答案正确。