顺序查找以及折半查找

data_structure

一、顺序查找

顺序查找的基本思路如下：

• 顺序扫描序列表
• 若匹配，返回下标
• 若不匹配，返回-1

//无监视哨的顺序查找
int SeqSearch(Record *r, int n, int k)
{
    int i = 0;
    while (i < n&&r[i].key != k)
        i++;
    if (i < n)
        return i;
    return -1;
}
//有监视哨的顺序查找
int SeqSearch2(Record *r, int n, int k)
{
    int i = 0;
    r[n].key = k;
    while (r[i].key != k)
        i++;
    if (i < n)
        return i;
    return -1;
}

测试结果:

二、折半查找

折半查找的基本思想是在有序表中，取中间元素作为比较对象。

• k==mid ， 成功
• k < mid ， 左半区继续查找
• k>mid ， 右半区继续查找

重复上述查找过程，直到查找成功，或所查找的区域无记录，查找失败。

//折半查找非递归算法
int BiSearch(Record r[], int n, int k)
{
    int low = 0;
    int high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (r[mid].key == k)
            return mid;
        else if (r[mid].key < k)
            low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}
//折半查找递归算法
int BiSearch2(Record r[], int low, int high, int k)
{
    if (low>high)
        return -1;
    else
    {
        int mid = (low + high) / 2;
        if (r[mid].key == k)
            return mid;
        else
            if (r[mid].key < k)
                return BiSearch2(r, mid + 1, high, k);
            else
                return BiSearch2(r, low, mid - 1, k);
    }
}

测试结果：