在我们开发中经常需要查找内容，那么我们如何利用更好的算法去实现查找的内容。
下面就介绍几种常用的查找算法。

第一种，顺序查找

顺序查找可能是我们开发中常用的一种之一，因为它实现的原理和方法很简单
以数组为例，查找数组中的一个元素

代码

//1、顺序查找
//a为数组，n为查找的数组个数，key为要查找的关键字

int Sequential_search(int *a,int n,int key){
    for (int i = 0; i<n; i++) {
        if(a[i] == key)
            return i;
    }
    return 0;
}

上面这种方法，实现起来很简单，但是效率很低，而且每一步都需要判断i是否在范围内
因此我们利用一个哨兵的思想去修改一下上面的方法

//2、利用哨兵查找
int Sequential_search2(int *a,int n,int key){
    int i;
    //让a[0] = key,哨兵
    a[0] = key;
    //循环从数组尾部开始
    i = n;
    while (a[i]!=key) {
        i--;
    }
    return i;
}

上面就是利用了数组中第一个元素，将查找的元素放在第一个元素，从尾到头进行查找。

折半查找（二分查找）

利用二分法来查找元素，比按顺序查找方便很多，实现起来也不复杂

代码

//3、折半查找算法
//假设数组a，已经是有序的（从小到大）
int Binary_Search(int *a,int n,int key){
    int low,hight,mid;
    //定义最低下标为记录首位
    low = 1;
    //定义最高下标为记录末位
    hight = n;
    while (low<=hight) {
        //折半计算
        mid = (low+hight)/2;
        if(key<a[mid]){
            //若key小于a[mid]，则将最高位设置为mid-1
            hight = mid-1;
        }else if (key>a[mid]){
            //若key大于a[mid]，则将最低位设置为mid+1
            low = mid+1;
        }else{
            //若相等，直接返回mid
            return mid;
        }
    }
    return 0;
}

插值查找

插值查找的算法思想还是利用了二分查找

其实就是改变了mid值的公式

15894394166909.png

代码

//4、插值查找
int Interpolation_Search(int *a,int n,int key){
    int low,hight,mid;
    //定义最低下标为记录首位
    low = 1;
    //定义最高下标为记录末位
    hight = n;
    while (low<=hight) {
        //折半计算
        mid = low+(hight-low)*(key+a[low])/(a[hight-a[low]]);
        if(key<a[mid]){
            //若key小于a[mid]，则将最高位设置为mid-1
            hight = mid-1;
        }else if (key>a[mid]){
            //若key大于a[mid]，则将最低位设置为mid+1
            low = mid+1;
        }else{
            //若相等，直接返回mid
            return mid;
        }
    }
    return 0;
}

斐波拉契查找

斐波拉契查找其实是再次利用了一个数组F，利用斐波拉契的性质记录每个位置的值。

1、利用两个变量记录low = 1，和hight = n
2、找到数组长度n在F中的位置j
3、将数组的长度增加到F数组的长度，增加的内容为数组最后一个元素。
4、两个变量之间进行查找，计算mid = low +F[j-1]-1;
5、比较key值和a[mid]的大小，若key大，low = mid+1，j=j-2，若key小，hight = mid-1，j = j-1，若相等，判断mid与n的大小，mid小，返回mid的值，否则返回n的值（说明是补全的函数）。

代码

//5、斐波拉契查找
int F[100];
int Fibonacci_search(int *a,int n,int key){
    int low,hight,i,j,mid;
    //最低位下标记录为首位
    low = 1;
    //最高位标记为记录末尾
    hight = n;
    j = 0;
    //1、计算n为斐波拉契数列位置
    while (n>F[j]-1) {
        j++;
    }
    //2、将数组a不满的位置不全值
    for (i = n; i<F[j]-1; i++) {
        a[i] = a[n];
    }
    while (low<=hight) {
        //计算当前分隔的下标
        mid = low+F[j-1]-1;
        
        if (key<a[mid]) {
            //若查找的记录小于当前分隔记录
            //将最高下标调整到分隔下标mid-1处
            hight = mid-1;
            //斐波拉契数列下标减1；
            j = j-1;
        }else if (key>a[mid]){
            //若查找的记录大于当前分隔记录
            //将最低下标调整到分隔下标mid-1处
            low = mid+1;
            //斐波拉契数列下标减2；
            j = j-2;
        }else{
            if(mid<=n){
                //若相等则说明，mid即为查找的位置
                return mid;
            }else{
                //若mid>n,说明是补全数值，返回n；
                return n;
            }
        }
    }
    return 0;
}

main函数和输出结果

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("静态查找!\n");
    int a[MAXSIZE+1],i,result;
    int arr[MAXSIZE] = {0,1,16,24,35,47,59,62,73,88,99};
    for (i = 0; i<=MAXSIZE; i++) {
        a[i] = i;
    }
    //1、顺序查找
    result = Sequential_search(arr, 10, 62);
    printf("顺序查找:%d\n",result);
    
    //2、顺序查找_哨兵
    result = Sequential_search2(arr, 10, 62);
    printf("顺序查找_哨兵:%d\n",result);
    
    //3、折半查找
    result = Binary_Search(arr, 10, 62);
    printf("折半查找:%d\n",result);
    
    //4、插值查找
    result = Interpolation_Search(arr, 10, 62);
    printf("插值查找:%d\n",result);
    
    //5、斐波拉契查找
    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, 62);
    
     printf("斐波拉契查找:%d\n",result);
    
    return 0;
}


输出结果

静态查找!
顺序查找:7
顺序查找_哨兵:7
折半查找:7
插值查找:7
斐波拉契查找:7
Program ended with exit code: 0

二叉排序树

之前我们探索过如何创建二叉树，现在我们用代码来实现一下二叉树的查找，插入，删除。

二叉树的插入是按照数值大小来进行排序的，因此我们需要对插入的值进行判断，以第一个元素为根节点，比根节点小的在树的左边，比根节点大的在树的右边

//1.二叉排序树-插入
/*  当二叉排序树T中不存在关键字等于key的数据元素时， */
/*  插入key并返回TRUE，否则返回FALSE */
int InsertBST(BiTree *T,int key){
    BiTree p,s;
    //1、若查找插入的值是否存在二叉树中，查找失败则插入
    if(!SearchBST(*T, key, NULL, &p)){
        //2、初始化节点s，并将key赋值给s，将s的左右孩子节点暂时设置为null
        s = (BiTree)malloc(sizeof(BiTree));
        s->data = key;
        s->lchild = s->rchild = NULL;
        //3、
        if(!p){
            //如果p为空，则将s作为二叉树新的根节点
            *T = s;
        }else if (key<p->data){
            //如果key<p->data，则将s插入右孩子
            p->lchild = s;
        }else
            //如果key>p->data，则将s插入为右孩子
            p->rchild = s;
        return TRUE;
    }
    return FALSE;
}

二叉树的搜索

//2.二叉排序树--查找
/*
 递归查找二叉排序树T中,是否存在key;
 指针f指向T的双亲,器初始值为NULL;
 若查找成功,则指针p指向该数据元素的结点,并且返回TRUE;
 若指针p指向查找路径上访问的最后一个结点则返回FALSE;
 */

int SearchBST(BiTree T,int key,BiTree f,BiTree *p){
    
    if(!T){
        //查找不成功
        *p = f;
        return FALSE;
    }else if (key ==T->data){
        //查找成功
        *p = T;
        return TRUE;
    }else if (key<T->data)
        //在左子树中继续查找
        return SearchBST(T->lchild, key, T, p);
    else
        //在右子树中继续查找
        return SearchBST(T->rchild, key, T, p);
    
    return 0;
}

二叉树的删除是一个比较复杂的操作，请神容易送神难，需要根据不同情况去实现删除操作
情况一：如果删除的节点只有右子树或左子树为空，将左子树或右子树的节点向上移动一位。
情况二：删除的节点即有左子树又有右子树。

如果遇到情况二的节点该如何去实现删除操作？

之前我们讲过二叉树的前序，中序，后序遍历，而之前的二叉树并不是按大小顺序来排序的，无法判断其遍历值的顺序。而二叉树如果按顺序插入，再用中序遍历，你会发现遍历的顺序是按照从小到达的次序排的。

因此，如果删除一个即有左子树又有右子树的节点，可以以中序遍历该数值的前一位或者后一位来代替它，以此来实现删除的便捷操作。

中序遍历二叉树的结果：
29 35 36 37 47 48 49 50 51 56 58 62 73 88 93 99

情况二的操作解释：

15894422954743.png

初始时：p -> 47,temp->47,s->35
查找s的右孩子: temp->35,s->37
赋值操作：p->data = s->data = 37

判断：temp与*p是否相等
相等情况是s没有右孩子节点，
因此将temp->lchild = s->lchild
不想等情况下
就将temp(35)->rchild(37) = s(37)->lchild(36)

代码

//3、从二叉排序树中删除节点p，并重新接它的左右子树
int Delete(BiTree *p){
    BiTree temp,s;
    //情况1:如果删除的节点右子树或左子树为空，将左子树或右子树的节点向上移动一位
    //情况2:删除的节点即有右子树又有左子树
    if((*p)->rchild == NULL){
        //情况一
        //将节点p存储到temp
        temp = *p;
        //将p指向p的左子树上
        *p = (*p)->lchild;
        //释放temp
        free(temp);
    }else if ((*p)->lchild == NULL){
        temp = *p;
        *p = (*p)->rchild;
        free(temp);
    }else{
        //情况二
        //1、将节点p存储到临时变量temp，并且让节点s指向p的左子树
        temp = *p;
        s = (*p)->lchild;
        //2、将指针s，向右到尽头，找到待删节点的前驱
        //在待删节点的左子树中，找到最大的一个节点（即在右边找到直接前驱）
        while (s->rchild) {
            temp = s;
            s = s->rchild;
        }
        //3、将要删除的节点p数据赋值成s->data
        (*p)->data = s->data;
        //4、重连子树
        //如果temp不等于p，则将s->lchild赋值给temp->rchild
        //如果temp等于p，则将s->lchild赋值给temp->rchild
        if(temp != *p)
            temp->rchild = s->lchild;
        else
            temp->lchild = s->lchild;
        
        //5、删除s指向的节点
        free(s);
    }
    
    return TRUE;
}

//4.查找结点,并将其在二叉排序中删除;
/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, */
/* 并返回TRUE；否则返回FALSE。 */
int DeleteBST(BiTree *T,int key){
    //不存在关键字等于key的数据元素
    if(!*T)
        return FALSE;
    else{
        //找到关键字等于key的元素
        if(key == (*T)->data)
            return Delete(T);
        else if (key<(*T)->data)
            return DeleteBST(&(*T)->lchild, key);
        else
            return DeleteBST(&(*T)->rchild, key);
    }
}

函数的调用和输出结果

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("二叉排序树!\n");
    int i;
    int a[10] = {62,88,58,47,35,73,51,99,37,93};
    BiTree T = NULL;
    
    for (i = 0; i<10; i++) {
        InsertBST(&T, a[i]);
    }
    
    BiTree p;
    int value = SearchBST(T, 99, NULL, &p);
    printf("查找%d是否成功:%d(1:成功/0:失败)\n",p->data,value);
    
    value = DeleteBST(&T, 93);
    printf("二叉树删除93是否成功:%d (1:成功/0:失败)\n",value);
    
    value = DeleteBST(&T, 47);
    printf("二叉树删除47是否成功:%d (1:成功/0:失败)\n",value);
    
    value = DeleteBST(&T, 12);
    printf("二叉树删除12是否成功:%d (1:成功/0:失败)\n",value);
    
    printf("\n\n");
    
    value = SearchBST(T, 93, NULL, &p);
    printf("查找93是否成功:%d (1:成功/0:失败)\n",value);
    
    value = SearchBST(T, 47, NULL, &p);
    printf("查找47是否成功:%d (1:成功/0:失败)\n",value);
    
    value = SearchBST(T, 99, NULL, &p);
    printf("查找99是否成功:%d (1:成功/0:失败)\n",value);
    
    return 0;
}


输出结果

二叉排序树!
查找99是否成功:1(1:成功/0:失败)
二叉树删除93是否成功:1 (1:成功/0:失败)
二叉树删除47是否成功:1 (1:成功/0:失败)
二叉树删除12是否成功:0 (1:成功/0:失败)


查找93是否成功:0 (1:成功/0:失败)
查找47是否成功:0 (1:成功/0:失败)
查找99是否成功:1 (1:成功/0:失败)
Program ended with exit code: 0

二叉树的遍历操作