查找就是根据给定的某个值，在查找表中确定一个其关键字等于给给定值的数据元素（或记录）。

查找表是由同一类型的数据元素（或记录构成的集合）。

关键字是数据元素中某个数据项的值。又称为键值，用它可以标志一个数据元素。也可以标志一个记录的某个数据项（字段），我们称为关键码。

若此关键字可以唯一地标志一个记录，则称此关键字为主关键字。那么对于那些可以识别多个数据元素（或记录）的关键字，我们称为次关键字。

查找表按照操作方式来分有两大种：静态查找表和动态查找表。

静态查找表

只做查找操作的查找表

• 查找某个“特定的”数据元素是否在查找表中
• 检索某个“特定的”数据元素和各种属性

动态查找表

在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中华删除已经存在的某个数据元素。

• 查找时插入数据元素
• 查找时删除数据元素

顺序查找

顺序查找又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

顺序表查找算法

#include <stdio.h>
#define MAXSIZE 100 /* 存储空间初始分配量 */

/* 无哨兵顺序查找，a为数组，n为要查找的数组个数，key为要查找的关键字 */
int Sequential_Search(int *a,int n,int key)
{
    int i;
    for(i=1;i<=n;i++)
    {
        if (a[i]==key)
            return i;
    }
    return 0;
}
 
int main(int argc, const char * argv[]) {
    
    int a[MAXSIZE+1],i,result;
    for(i=0;i<=MAXSIZE;i++) {
        a[i]=i;
    }
    result=Sequential_Search(a,MAXSIZE,66);
    printf("Sequential_Search:%d \n",result);
    
    return 0;
}

顺序表查找优化

/* 有哨兵顺序查找 */
int Sequential_Search2(int *a,int n,int key)
{
    int i;
    a[0]=key;
    i=n;
    while(a[i]!=key)
    {
        i--;
    }
    return i;
}

有序表查找

折半查找

折半查找技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

#include <stdio.h>
#define MAXSIZE 100 /* 存储空间初始分配量 */

/* 折半查找 */
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
            return mid;        /* 若相等则说明mid即为查找到的位置 */
    }
    return 0;
}

int main(int argc, const char * argv[]) {
    
    int result;
    int arr[MAXSIZE]={0,1,16,24,35,47,59,62,73,88,99};
    
    result=Binary_Search(arr,10,62);
    printf("Binary_Search:%d \n",result);
    
    return 0;
}

插值查找

插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式：(key - a[low]) / (a[heigh] - a[low])。

mid的计算公式：mid = low + (heigh - low) * (key - a[low]) / (a[heigh] - a[low])

#include <stdio.h>
#define MAXSIZE 100 /* 存储空间初始分配量 */

/* 插值查找 */
int Interpolation_Search(int *a,int n,int key)
{
    int low,high,mid;
    low=1;     /* 定义最低下标为记录首位 */
    high=n;    /* 定义最高下标为记录末位 */
    while(low<=high)
    {
        mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */
        if (key<a[mid])        /* 若查找值比插值小 */
            high=mid-1;        /* 最高下标调整到插值下标小一位 */
        else if (key>a[mid])   /* 若查找值比插值大 */
            low=mid+1;         /* 最低下标调整到插值下标大一位 */
        else
            return mid;        /* 若相等则说明mid即为查找到的位置 */
    }
    return 0;
}

int main(int argc, const char * argv[]) {
    
    int result;
    int arr[MAXSIZE]={0,1,16,24,35,47,59,62,73,88,99};
    
    result=Interpolation_Search(arr,10,62);
    printf("Binary_Search:%d \n",result);
    
    return 0;
}

斐波那契查找

#include <stdio.h>
#define MAXSIZE 100 /* 存储空间初始分配量 */
int F[100];         /* 斐波那契数列 */

/* 斐波那契查找 */
int Fibonacci_Search(int *a,int n,int key)
{
    int low,high,mid,i,k=0;
    low=1;                         /* 定义最低下标为记录首位 */
    high=n;                        /* 定义最高下标为记录末位 */
    while(n>F[k]-1)                /* 计算n位斐波那契数列的位置 */
        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])            /* 若查找记录小于当前分割记录 */
        {
            high=mid-1;            /* 最高下标调整到分割下标mid-1处 */
            k=k-1;                 /* 斐波那契数列下标减一位 */
        }
        else if (key>a[mid])       /* 若查找记录大于当前分割记录 */
        {
            low=mid+1;             /* 最低下标调整到分割下标mid+1处 */
            k=k-2;                 /* 斐波那契数列下标减两位 */
        }
        else
        {
            if (mid<=n)
                return mid;         /* 若相等则说明mid即为查找到的位置 */
            else
                return n;           /* 若mid>n说明是补全数值，返回n */
        }
    }
    return 0;
}

int main(int argc, const char * argv[]) {
    
    int i,result;
    int arr[MAXSIZE]={0,1,16,24,35,47,59,62,73,88,99};
    
    F[0]=0;
    F[1]=1;
    for(i = 2;i < 100;i++)
    {
        F[i] = F[i-1] + F[i-2];
    }
    result=Fibonacci_Search(arr,10,59);
    printf("Fibonacci_Search:%d \n",result);
    
    return 0;
}

查找的核心在于：

1. 当 key=a[mid] 时，查找成功。
2. 当 key<a[mid] 时，新范围是第 low 个到第 mid-1 个，此时范围个数为 F[k-1]-1 个。
3. 当 key>a[mid] 时，新范围是第 m+1 个到第 high 个，此时范围个数为 F[k-2]-1 个。

线性索引查找

索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项组成，每个索引项至少应包含关键字和其对应的记录在存储中的位置等信息。

索引按照结构可以分为线性索引、树形索引和多级索引。

线性索引

就是将索引项集合组织为线性结构，也称为索引表。

稠密索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。
对于稠密索引这个索引表来说，索引项一定是按照关键码有序排列的。

分块索引

分块有序，是把数据集的记录分成了若干块，并且这些块需要满足以下两个条件：

• 块内无序：即每一块内的记录不要求有序。
• 块间有序：例如，要求第二块所有记录的关键字均要大于第一块中所有记录的关键字，第三块所有记录的关键字均要大于第二块中所有记录的关键字......因为只有块间有序，才有可能在查找时提高效率。

对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。

倒排索引

二叉排序树

二叉排序树，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值。
• 若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值。
• 它的左、右子树也分别为二叉排序树。

/* 二叉树的二叉链表结点结构定义 */
typedef  struct BiTNode /* 结点结构 */
{
    int data;   /* 结点数据 */
    struct BiTNode *lchild, *rchild;    /* 左右孩子指针 */
} BiTNode, *BiTree;