算法：顺序查找与折半查找

资料摘自：<数据结构c++语言描述>

typedef int DataType;

//顺序查找算法
//用顺序查找在n元数组list中查找与key等值的元素，返回该数组元素的下标
//若未找到，则返回-1
int SeqSearch(DataType List[], int n, DataType key)
{
    for(int i = 0; i < n; i++)
    {
        if(List[i] == key)
        {
            return i;
        }
    }
    return -1;
}
/*
*顺序查找的复杂度在最好情况和最差情况下差别很大。最好情况是表中第一个元素既是要找的元素，其运算时间为O(1)。
*最差情况是直到找到表中最后一个元素或要找的元素根本不存在，这时需查找所有n个元素，其复杂度为O(n)。一般情况
*下查找的次数要少一些。对于随机表，等值元素可能在表的任何位置发现。在执行次数足够多时，找到等值的平均查找长
*度为n/2，即n/2是预期的查找次数。因此，我们说顺序查找算法的平均性能为O(n)。
*/

//折半查找
/*
*顺序查找可适用于任意表。若被查找的表有序，则可用折半查找算法来查找，它是一种改进的查找算法。人们在电话号码
*簿中查找电话号码的方法就用的是折半查找算法，他们一般根据给定姓名的首字符来查找号码中的前、中、后部分，也许
*幸运地就找到了相应的页码。若没找到，也可根据姓名的相对位置往前或往后查找号码簿。例如，若要查找的人的姓名以
*"R"开头，而此时你翻开的页为"T"，则应向前翻。重复这个操作直到找到相应的电话号码或者确定号码簿中没有这个姓名。
*这也是我们用来查找有序表的办法。首先找到表中的中间元素，将其值与我们要求的值进行比较，若不等，则根据该值与
*要找值的大小来决定查表的前半部分或后半部分。通常情况下，如果表有序的话，可用这个算法来缩短查找时间。
*假定表以数组形式存放。数组中有n个元素，其下标范围为low=0和hight=n-1，则折半查找算法可描述如下：
*/
//用折半查找算法在一有序数组中查找key值。若找到，返回其下标值，否则返回-1
int BinSearch(DataType list[], int low, int high, DataType key)
{
    int mid;
    DataType midvalue;
    while(low <= high)
    {
        mid = (int)(low + high) / 2;
        midvalue = list[mid];
        if(key == midvalue)
        {
            return mid;
        }else if(key < midvalue){
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    return -1;
}