查找表是由同一类型的数据元素构成的集合。由于集合中的数据元素之间存在着完全松散的换洗，因此查找表是一种非常领边的数据结构。

对查找表经常进行的操作：

• 查询某个特定的数据元素是否在查找表中；
• 检索某个特定的数据元素的各种属性；
• 在查找表中插入一个数据元素；
• 在查找表中删去某个数据元素；

静态查找表（Static search table）

顺序表的查找

顺序查找（Sequential Search）的查找过程：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若知道第一个记录，其关键字和给定值比较不相等，则表明表中没有所查记录，查找不成功。

// 顺序查找
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_Search_Guard(int *a, int n, int key) {
    int i = n;
    a[0] = key;
    while (a[i] != key) {
        i--;
    }
    return i;
}

有序表的查找

折半查找（Binary Search）的查找过程：先确定待查找记录所在的范围，然后珠逐步缩小范围直到找到或找不到该记录为止。

// 折半查找算法
int Binary_Search(int *a, int n, int key) {
    int mid;
    int low = 0;
    int high = n;
    while (low <= high) {
        mid = (high + low) >> 1;
        if (key < a[mid]) {
            high = mid - 1;
        } else if (key > a[mid]) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return 0;
}

// 插值查找
int Interpolation_Search(int *a, int n, int key) {
    int mid;
    int low = 0;
    int 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;
        }
    }
    return 0;
}

//5.斐波拉契查找
int F[100]; /* 斐波那契数列 */
int Fibonacci_Search(int *a, int n, int key) {
    int low, high, mid, i, k;
    low = 1;
    high = n;
    k = 0;
    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]) {
            high = mid - 1;
            k = k - 1;
        } else if(key > a[mid]){
            low = mid + 1;
            k = k - 2;
        } else {
            if (mid <= n) {
                return mid;
            } else {
                return n;
            }
        }
    }
    return 0;
}

动态查找表 （Dynamic search table）

二叉排序树（Binary sort Tree）或者是一颗空树；或者是具有下列性质的二叉树；

1. 若它的左子树不空，则左子树上所有结点的值均小于它的跟结点的值；
2. 若它的右子树不空，则右子树上所有结点的值均大于它的跟结点的值；
3. 它的左、右子树也分别为二叉树排序树；

代码实现

typedef int Status;

typedef  struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 二叉排序树--查找
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p) {
    if (!T) {
        *p = f;
        return FALSE;
    }
    
    if (T->data == key) {
        *p = T;
        return TRUE;
    } else if (key < T->data) {
        return SearchBST(T->lchild, key, T, p);
    } else {
        return SearchBST(T->rchild, key, T, p);
    }
}

Status InsertBST(BiTree *T, int key) {
    BiTree p, s;
    if (!SearchBST(*T, key, NULL, &p)) {
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        
        if (!p) {
            *T = s;
        } else if (key < p->data) {
            p->lchild = s;
        } else {
            p->rchild = s;
        }
        return TRUE;
        
    }
    return FALSE;
}

// 从二叉排序树中删除结点p,并重接它的左或者右子树;
Status Delete(BiTree *p){
    BiTree temp, s;
    if((*p)->rchild == NULL) {
        temp = *p;
        *p = (*p)->lchild;
        free(temp);
    } else if((*p)->lchild == NULL) {
        temp = *p;
        *p = (*p)->rchild;
        free(temp);
    } else {
        temp = *p;
        s = (*p)->lchild;
        while (s->rchild) {
            temp = s;
            s = s->rchild;
        }
        (*p)->data = s->data;
        
        if(temp != *p)
            temp->rchild = s->lchild;
        else
            temp->lchild = s->lchild;
        free(s);
    }
    
    return  TRUE;
}

// 查找结点,并将其在二叉排序中删除;
Status DeleteBST(BiTree *T, int key) {
    if(!*T) {
        return FALSE;
    } else {
        if (key == (*T)->data)
            return Delete(T);
        else if (key < (*T)->data)
            return DeleteBST(&(*T)->lchild, key);
        else
            return DeleteBST(&(*T)->rchild, key);
    }
}