数据结构-查找

image.png

• 数据元素：是组成数据的、有一定意义的基本单位，也被称为纪录。
• 查找表：由同一类型的数据元素(或记录)构成的集合。

按操作方式分类：
静态查找表：只做查找操作的查找表。
动态查找表：在查找过程中同时插入查找表中不存在的数据元素或者从查找表中删除已经存在的某个数据元素。

• 关键字：数据元素(或记录)中某个数据项的值，用来标识(或识别)一个数据元素(或数据)。

主关键字：唯一识别一个数据元素(或数据)。
次关键字：可以识别多个数据元素(或数据)。

• 查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的纪录或数据元素。
• 顺序查找(线性查找)：从表中第一个(或最后一个)纪录开始，逐个进行纪录的关键字和给定值比较，若某个纪录的关键字和给定值相等，则查找成功；若直到最后一个(或第一个)，其关键字和指定值都不相等，则表中没有所查的纪录，查找失败。

/* a为数组，n为要查找的数组长度，key为要查找的关键字 */
int Sequential_Search(int *a, int n, int key){

    for (int i = 1; i <= n; i++){

        if (a[i] == key)

            return i;
    }
    return 0;
}

顺序查找优化(有哨兵顺序查找)：

int Sequential_Search2(int *a, int n, int key){

    int i;
    /* 设置a[0]为关键字值，我们称之为“哨兵” */
    a[0] = key; 

    /* 循环从数组尾部开始 */
    i = n;     
    while (a[i] != key){

        i--;
    }
    /* 返回0则说明查找失败 */
    return i;   
}

时间复杂度：O(n)

• 有序表查找：折半查找、插值查找、斐波那契查找

它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。

1. 折半查找(二分查找)：
   折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

   
   image.png

int Binary_Search(int *a, int n, int key){

    int low, high, mid;

    /* 定义最低下标为记录首位 */
    low = 1;                   

    /* 定义最高下标为记录末位 */
    high = n;                   

    while (low <= high){

        /* 折半 */
        mid = (low + high) / 2; 

        /* 若查找值比中值小 */
        if (key < a[mid])       

          /* 最高下标调整到中位下标小一位 */
          high = mid - 1;     

        /* 若查找值比中值大 */
        else if (key > a[mid]) 

            /* 最低下标调整到中位下标大一位 */
            low = mid + 1; ”

        else

            /* 若相等则说明mid即为查找到的位置 */
            return mid;         
    }

    return 0;
}

时间复杂度：O(logn)

2. 插值查找：

mid = 1/2* (high+low) = low + 1/2*(high-low)

mid = low + (key-a[low])/(a[high]-a[low])*(high-low);

时间复杂度：O(logn)

3. 斐波那契查找：

int Fibonacci_Search(int *a, int n, int key){

    int low, high, mid, i, k;

    /*定义最低下标为记录首位 */
    low = 1;                       

    /*定义最高下标为记录末位 */
    high = n;                     

    k = 0;

    /* 计算n位于斐波那契数列的位置 */
    while (n > F[k] - 1)           
        k++;

    /* 将不满的数值补全 */
    for (i = n; i < F[k] - 1; i++) 
      a[i] = a[n];

    while (low <= high){

        /* 计算当前分隔的下标 */
        mid = low + F[k - 1] - 1; 

        /* 若查找记录小于当前分隔记录 */
        if (key < a[mid]){

            /* 最高下标调整到分隔下标mid-1处 */
            high = mid - 1;       

            /* 斐波那契数列下标减一位 */
            k = k - 1;             
        }

        /* 若查找记录大于当前分隔记录 */
        else if (key > a[mid]){

            /* 最低下标调整到分隔下标mid+1处 */”
            low = mid + 1;

            /* 斐波那契数列下标减两位 */
            k = k - 2; 

        }else{

            if (mid <= n)

                /*若相等则说明mid即为查找到的位置*/
                return mid;       

            else

                /* 若mid>n说明是补全数值，返回n */
                return n;         
        }
    }

    return 0;
}

从指定数组中查找59

0	1	2	3	4	5	6	7	8	9	10
0	1	16	24	35	47	59	62	73	88	99

0	1	2	3	4	5	6	7	8	9	10
0	1	1	2	3	5	8	13	21	34	55

k	mid=low + F[k - 1] - 1	low=mid+1	high=mid-1	k
/	/	1	10	／
7	1 + F[6] - 1 = 8	1	7	6
6	1 + F[5] - 1 = 5	6	7	4
4	6 + F[3] - 1 = 7	6	6	3
3	6 + F[2] - 1 = 6	6	6	3

image.png image.png image.png image.png