1.问题描述
给定一个长度为n的数组A，查找元素x是否在A中。
2.解决方案描述
一种最直接的方法是扫描A中的所有项目，将每个项目与x比较，如果找到相等的项目A[i]，则返回数组下标i，否则返回-1，表示没找到。这种方法成为顺序搜索，由于元素比较的最大次数和序列的大小成线性关系，所以又称为线性搜索。
3.算法的代码表示
复制代码
1 ///
2 /// 线性搜索
3 ///
4 /// 搜索的源数组
5 /// 要搜索的值
6 /// 如果找到该值，返回该值所在的数组下标；否则返回-1
7 static int LinearSearch(int[] array, int x)
8 {
9 int i = 0;
10 while (i < array.Length)
11 {
12 if (x == array[i]) return i;
13 i++;
14 }
15 return -1;
16 }
复制代码
4.算法的调用
复制代码
1 static void Main(string[] args)
2 {
3 int[] TestArray = { 10, 2, 9, 5, 6, 3 };
4 Console.WriteLine("测试数组为：");
5 for (int i = 0; i < TestArray.Length; i++)
6 {
7 Console.Write("{0} ", TestArray[i]);
8 }
9 Console.WriteLine("\r\n请输入你要查找的整数：");
10 string TargetNum = Console.ReadLine();
11 int Num;
12 while (!int.TryParse(TargetNum, out Num))
13 {
14 Console.WriteLine("你的输入不合法！\r\n请输入你要查找的整数：");
15 TargetNum = Console.ReadLine();
16 }
17 int Result = LinearSearch(TestArray, Num);
18 if (Result != -1)
19 Console.WriteLine("你查找的数字在该数组的下标为：{0}", Result);
20 else
21 Console.WriteLine("在该数组中找不到你输入的数字");
22 Console.Read();
23 }
复制代码
5.算法分析
直观上，如果数组是无序的，那么扫描A中所有元素是不可避免的。但是如果数组是有序的，那么扫描A中所有元素则不是最佳选择。比如数组为{1,2,3,4,5,6}，如果我要搜索6是否在数组中，那么我将要扫描6次，这是最耗时的搜索。
那么如何保证在最短时间内找到有序数组里的元素呢？下节见分晓。