15、考研必会的查找算法u0026考研真题实战

本章需要掌握：

1、顺序查找
2、折半查找
3、二叉排序树原理及建树
4、二叉排序树删除
5、真题

1、顺序查找

一个简单的加了哨兵的查找顺序表，上面是核心，下面是实践

int Search_Seq(SSTable ST,ElemType key)
{
    ST.elem[0]=key;
    for(int i=ST.TableLen-1;ST.elem[i]!=key;i--);
    return i;
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct {
    ElemType* elem;//整型指针，申请的堆空间的起始地址存入elem
    int TableLen;//存储动态数组里边元素的个数
}SSTable;

void ST_Init(SSTable &ST,int len)
{
    //多申请了一个位置,为了存哨兵,不使用哨兵也可以，为了和王道书保持一致
    ST.TableLen=len+1;
    ST.elem= (ElemType*)malloc(sizeof(ElemType)*ST.TableLen);
    int i;
    srand(time(NULL));//随机数生成,考研不需要掌握
    for (i = 1; i < ST.TableLen; i++)//因为第0个是哨兵，所以从1随机
    {
        ST.elem[i] = rand() % 100;//为了随机生成的数都在0到99之间
    }
}
//打印顺序表
void ST_print(SSTable ST)
{
    int i;
    for(i=1;i<ST.TableLen;i++)
    {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}

int Search_Seq(SSTable ST,ElemType key)
{
    ST.elem[0]=key;//key存在零号位置，作为哨兵，有了这个，我们在循环时，可以少写一个i>=0判断
    int i;
    for(i=ST.TableLen-1;ST.elem[i]!=key;i--);//从后往前找，找到了，i就是刚好是对应的位置
    return i;
}
//顺序查找
int main() {
    SSTable ST;
    ST_Init(ST, 10);
    ST_print(ST);//打印顺序表中元素
    ElemType key;
    printf("please input search key:\n");
    scanf("%d",&key);
    int pos;
    pos = Search_Seq(ST, key);
    if(pos)
    {
        printf("find key,pos=%d\n",pos);
    }else{
        printf("not find\n");
    }
    return 0;
}

2、折半查找

一个简单的排序顺序表的，上面是核心，下面是实践

int BinarySearch(SSTable L, ElemType key)
{
    int low=0;
    int high=L.TableLen-1;
    int mid;
    while(low<=high)//low<=high，可以让mid既能取到low，也能取到high
    {
        mid=(low+high)/2;
        if(key>L.elem[mid])//如果目标值大于中位数
        {
            low=mid+1;
        } else if(key<L.elem[mid])
        {
            high=mid-1;
        }else{
            return mid;
        }
    }
    return -1;
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct {
    ElemType* elem;//整型指针
    int TableLen;//存储动态数组里边元素的个数
}SSTable;


//init进行了随机数生成，折半查找我们没有使用哨兵
void ST_Init(SSTable& ST, int len)
{
    ST.TableLen = len;
    ST.elem = (ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
    int i;
    srand(time(NULL));//随机数生成
    for (i = 0; i < ST.TableLen; i++)
    {
        ST.elem[i] = rand() % 100;
    }
}
void ST_print(SSTable ST)
{
    for (int i = 0; i < ST.TableLen; i++)
    {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}
//实现二分查找
int BinarySearch(SSTable L, ElemType key)
{
    int low=0;
    int high=L.TableLen-1;
    int mid;
    while(low<=high)//low<=high，可以让mid既能取到low，也能取到high
    {
        mid=(low+high)/2;
        if(key>L.elem[mid])//如果目标值大于中位数
        {
            low=mid+1;
        } else if(key<L.elem[mid])
        {
            high=mid-1;
        }else{
            return mid;
        }
    }
    return -1;
}
//函数名中存储的是函数的入口地址，也是一个指针，是函数指针类型
//left指针和right指针是指向数组中的任意两个元素
//qsort规定如果left指针指向的值大于right指针指向的值，返回正值，小于，返回负值，相等返回0
int compare(const void *left, const void *right)
{
    return *(int*)left-*(int*)right;
    //return *(ElemType*)right - *(ElemType*)left;//从大到小排序
}
//二分查找
int main() {
    SSTable ST;
    ST_Init(ST,10);//初始化，随机10个元素
    ST_print(ST);
    qsort(ST.elem,ST.TableLen,sizeof(ElemType),compare);//排序
    ST_print(ST);
    ElemType key;
    printf("please input search key:\n");
    scanf("%d",&key);
    int pos=BinarySearch(ST,key);
    if(pos!=-1)
    {
        printf("find key %d\n",pos);
    }else{
        printf("not find\n");
    }
    return 0;
}

3、二叉排序树原理及建树

二叉排序树满足①左子树非空，左子树结点小于根节点②右子树非空，右子树结点大于根节点③左右子树也是一颗二叉排序树

下面有递归创建和非递归创建的代码，不难理解，思路简单容易上手。

#include <stdio.h>
#include <stdlib.h>


typedef int KeyType;
typedef struct BSTNode{
	KeyType key;
	struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;

// 王道书上的递归写法，代码简单，但是理解有难度
int BST_Insert1(BiTree &T,KeyType k)
{
    if(NULL==T)
    {	//为新节点申请空间，第一个结点作为树根，后面递归再进入的不是树根，是为叶子结点
        T=(BiTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;//代表插入成功
    }
    else if(k==T->key)
        return 0;//发现相同元素，就不插入
    else if(k<T->key)//如果要插入的结点，小于当前结点
        //函数调用结束后，左孩子和原来的父亲会关联起来，巧妙利用了引用机制
        return BST_Insert1(T->lchild,k);
    else
        return BST_Insert1(T->rchild,k);
}

//54,20,66,40,28,79,58
//非递归的创建二叉查找树
int BST_Insert(BiTree& T,KeyType k)
{
    BiTree TreeNew= (BiTree)calloc(1,sizeof(BSTNode));//新结点申请空间
    TreeNew->key=k;//把值放入
    if(NULL==T)//树为空，新结点作为树的根
    {
        T=TreeNew;
        return 1;
    }
    BiTree p=T,parent;//p用来查找树
    while(p)
    {
        parent=p;//parent用来存p的父亲
        if(k>p->key)
        {
            p=p->rchild;
        }else if(k<p->key)
        {
            p=p->lchild;
        }else{
            return 0;//相等的元素不可以放入查找树，考研不会考相等元素放入问题
        }
    }
    //接下来要判断放到父亲的左边还是右边
    if(k>parent->key)//放到父亲右边
    {
        parent->rchild=TreeNew;
    }else{//放到父亲左边
        parent->lchild=TreeNew;
    }
    return 1;
}
//树中不放
void Creat_BST(BiTree& T,KeyType* str,int len)
{
    int i;
    for(i=0;i<len;i++)
    {
        BST_Insert(T,str[i]);//把某一个结点放入二叉查找树
    }
}

void InOrder(BiTree T)
{
    if(T!=NULL)
    {
        InOrder(T->lchild);
        printf("%3d",T->key);
        InOrder(T->rchild);
    }
}

BiTree BST_Search(BiTree T,KeyType k,BiTree &parent)
{
    parent=NULL;
    while(T!=NULL&&k!=T->key)
    {
        parent=T;
        if(k>T->key)
        {
            T=T->rchild;
        }else{
            T=T->lchild;
        }
    }
    return T;
}



//二叉排序树新建，中序遍历，查找
int main() {
    BiTree T=NULL;//树根
    KeyType str[7]={54,20,66,40,28,79,58};//将要进入二叉排序树的元素值
    Creat_BST(T,str,7);
    InOrder(T);//中序遍历二叉查找树是由小到大的
    printf("\n");
    BiTree search,parent;
    search=BST_Search(T,40,parent);
    if(search)
    {
        printf("find key %d\n",search->key);
    }else{
        printf("not find\n");
    }
    return 0;
}

4、二叉排序树删除

一个有梯子可以打开的演示网站：二叉排序树删除节点展示

不是很难，简单画下图就能理解

//这个书上没有二叉排序树删除代码--考大题没那么高
void DeleteNode(BiTree &root,KeyType x)
{
    if(NULL==root)
    {
        return;
    }
    if(root->key>x)//当前结点大于要删除的结点，往左子树找
    {
        DeleteNode(root->lchild,x);
    }else if(root->key<x)//当前结点小于要删除的结点，往右子树找
    {
        DeleteNode(root->rchild,x);
    }else{//找到了要删除的结点
        if(root->lchild==NULL)//左子树为空，右子树直接顶上去
        {
            BiTree tempNode=root;
            root=root->rchild;
            free(tempNode);
        }else if(root->rchild==NULL)//右子树为空，左子树直接顶上去
        {
            BiTree tempNode=root;
            root=root->lchild;
            free(tempNode);
        }else{//两边都不为空
            //一般的删除策略是左子树的最大数据 或 右子树的最小数据
            // 代替要删除的节点(这里采用查找左子树最大数据来代替，最大数据是左子树的最右结点)
            BiTree tempNode=root->lchild;
            while(tempNode->rchild!=NULL)
            {
                tempNode=tempNode->rchild;
            }
            root->key=tempNode->key;//把tempNode对应的值替换到要删除的值的位置上
            DeleteNode(root->lchild,tempNode->key);//在左子树中找到tempNode的值，把其删除
        }
    }
}

5、真题

42.(15 分)一个长度为 L(L≥1)的升序序列 S，处在第 [L/2]个位置的数称为 S 的中位数。例如，若序列 S1 = (11, 13, 15, 17, 19)，则 S1 的中位数是 15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S2 = (2, 4, 6, 8, 20)，则 S1 和 S2 的中位数是 11。现在有两个等长升序序列 A 和 B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。要求:

(1)给出算法的基本设计思想。
(2)根据设计思想，采用 C、C++或 Java 语言描述算法，关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

这个题目所考察的内容是二分查找，但是有两个数组，是双数组的二分查找，是一道非常经典的题目。因为空间尽可能高效，因此我们不能够去再搞一个大数组，把两个数组合并到一起，这样得分会非常低。
(1)算法的基本设计思想如下:

分别求出序列 A 和 B 的中位数，设为 a 和 b，求序列 A 和 B 的中位数过程如下: (1)若 a=b，则 a 或 b 即为所求中位数，算法结束。
(2)若 a<b，则舍弃序列 A 中较小的一半，同时舍弃序列 B 中较大的一半,要求舍弃的长度相等;
(3)若 a>b，则舍弃序列 A 中较大的一半，同时舍弃序列 B 中较小的一半，要求舍弃的长度相等;
在保留的两个升序序列中，重复(1)(2)(3)，直到序列中只含一个数，较小者是中位数。

我的代码

#include <iostream>

int MidSearch(int* A,int* B,int n)
{
    //分别表示序列 A 和 B 的首位数、末位数和中位数，s是start简写，d是end简写
    int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
    //循环判断结束条件是，两个数组均不断删除最后均只能剩余一个元素
    while(s1!=d1||s2!=d2)
    {
        m1 = (s1 + d1) / 2;
        m2 = (s2 + d2) / 2;
        if(A[m1]==B[m2])
        {
            return A[m1];//满足条件 1
        }else if(A[m1]<B[m2])//满足条件2
        {
            if((s1 + d1) % 2 == 0) { //若元素个数为奇数,这里注意数组下标从0开始
                s1=m1;//舍弃 A 中间点以前的部分且保留中间点
                d2=m2;//舍弃 B 中间点以后的部分且保留中间点
            }else{//元素个数为偶数
                s1=m1+1;//舍弃 A 中间点及中间点以前部分
                d2=m2;//舍弃 B 中间点以后的部分且保留中间点
            }
        }else{//满足条件 3），下面的操作和上面条件2是完全对称的
            if ((s1 + d1) % 2 == 0) { //若元素个数为奇数
                d1=m1;//舍弃 A 中间点以后的部分且保留中间点
                s2=m2;//舍弃 B 中间点以前的部分且保留中间点
            }else{//元素个数为偶数
                d1=m1; //舍弃 A 中间点以后部分且保留中间点
                s2=m2+1;//舍弃 B 中间点及中间点以前部分
            }
        }
    }
    return A[s1] < B[s2] ? A[s1] : B[s2];//因为题目要的是11，因此我们拿小的那个
}

//2011年42题
int main() {
    int A[] = { 11,13,15,17,19};//我们也可以分别把A和B都变为偶数个元素来测试
    int B[] = { 2,4,6,8,20};
    int mid = MidSearch(A, B, 5);
    printf("mid=%d\n", mid);
    return 0;
}