第4章 基本查找算法
數據查找是一項基本的計算機編程任務而且也已被研究多年。本章僅僅研究查找問題的一個方面 – 在列表（數組）中查找給定的值。
在列表中查找數據有兩種基本方式：順序查找與二分查找。當列表中的項是隨機排列時適用順序查找；二分查找適用於已排好序的列表。
順序查找
這種最顯而易見的查找類型由一個記錄集的起始部分開始，遍歷每一個記錄直到找到你要找的記錄或著你來到記錄的尾部。這就叫做順序查找。
順序查找（又稱線性查找）很簡單易行。由數組開始部分起比較每一個正訪問的數組元素與你要查找的值。如果你找到匹配的元素，查找結束。如果到達數組的末尾也無法得到一個匹配，則表明數組中無此值。
順序查找的函數如下：
bool SeqSearch(int[] arr, int sValue)
{
for (int index = 0; index < arr.Length - 1; index++)
if (arr[index] == sValue)
return true;
return false;
}
如果有一個匹配被找到，程序立即返回True並退出。如果到數組的尾部函數仍未返回True，則待查找的值不在數組中且函數返回False。
如下是一個測試我們順序查找實現的程序：
using System;
using System.IO;
public class Chapter4
{
static void Main()
{
int[] numbers = new int[100];
StreamReader numFile = File.OpenText("c:\numbers.txt");
for (int i = 0; i < numbers.Length - 1; i++)
numbers[i] = Convert.ToInt32(numFile.ReadLine(), 10);
int searchNumber;
Console.Write("Enter a number to search for: ");
searchNumber = Convert.ToInt32(Console.ReadLine(), 10);
bool found;
found = SeqSearch(numbers, searchNumber);
if (found)
Console.WriteLine(searchNumber + " is in the array.");
else
Console.WriteLine(searchNumber + " is not in the array.");
}
static bool SeqSearch(int[] arr, int sValue)
{
for (int index = 0; index < arr.Length - 1; index++)
if (arr[index] == sValue)
return true;
return false;
}
}
這個程序首先由一個文本文件讀取一個數據集。這個數集包含100個整數，以部分隨機的順序存儲於一個文件中。然後程序提示用戶輸入一個待查找的數字，並調用SeqSearch函數來執行查找。
你也可以編寫一個這樣的順序查找函數 – 當查找到待查找的值時返回其索引，反之如果找不到返回-1。首先，我們看一下新的函數：
static int SeqSearch(int[] arr, int sValue)
{
for (int index = 0; index < arr.Length - 1; index++)
if (arr[index] == sValue)
return index;
return -1;
}
下面的程序使用了這個函數：
using System;
using System.IO;
public class Chapter4
{
static void Main()
{
int[] numbers = new int[100];
StreamReader numFile = File.OpenText("c:\numbers.txt");
for (int i = 0; i < numbers.Length - 1; i++)
