顺序查找

说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

复杂度分析： 查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
当查找不成功时，需要n次比较，时间复杂度为O(n);
所以，顺序查找的时间复杂度为O(n)。

C++实现源码：

1
2
3
4
5
6
7
8
9
//顺序查找
int SequenceSearch(int a[], int value, int n)
{
    int i;
    for(i=0; i<n; i++)
        if(a[i] == value)
            return i;
    return -1;
}

二分查找

说明：元素必须是有序的，如果是无序的则要先进行排序操作。

基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

复杂度分析：最坏情况下，关键词比较次数为 [公式] （ [公式] 取下整），且期望时间复杂度为 [公式] ；

折半查找是一棵二叉排序树，每个根结点的值都大于左子树的所有结点的值，小于右子树所有结点的值。

例如：长度为10的有序表的平均查找长度为：ASL=(11+22+34+43)/10=29/10=2.9;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void BinarySearch2() {
    //二分查找（折半查找），循环实现
int BinarySearch1(int a[], int value, int n)
{
    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        else if(a[mid]>value)
            high = mid-1;
        else if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}

//二分查找，递归实现
int BinarySearch2(int a[], int value, int low, int high)
{
    if(low <= high)
    {
        int mid = low+(high-low)/2;
        if(a[mid]==value)
            return mid;
        else if(a[mid]>value)
            return BinarySearch2(a, value, low, mid-1);
        else if(a[mid]<value)
            return BinarySearch2(a, value, mid+1, high);
    }
    else
        return -1;
}
}

插值查找

二分查找的升级版本；添加了一个比例参数用以调整每次查找区间的大小。

int mid = low+（value-a[low])/(a[high]-a[low])*(high-low);

基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 关键代码
int value ; //比例参数
int mid = low+（value-a[low])/(a[high]-a[low])*(high-low);

//插值查找
int InsertionSearch(int a[], int value, int low, int high)
{
    if(low <= high)
    {
        int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            return InsertionSearch(a, value, low, mid-1);
        if(a[mid]<value)
            return InsertionSearch(a, value, mid+1, high);
    }
    else
        return -1;
}