六、查找

顺序查找

1
2
3
4
5
6
int Search(int a[],int n,int k){
    for(int i = 1;i <= n; ++i)
        if(a[i] == k)
            return 1;
    return 0;
}

折半查找（二分查找）

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
int	BSearch(int a[],int l,int r,int k){
    int mid;
    while(l < r){
        mid = (l + r) / 2;
        if(a[mid] == k)
            return mid;
        if(a[mid] > k)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return 0;
}

分块查找

时间复杂度：img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef struct{
    int key;
    int low,high;	//记录某块中第一个和最后一个元素的位置
}indexElem;
indexElem index[MaxSize];	//定义索引表
//k是需要查找的数字  arr[]表示原数组  index是结构体类型的索引表
int Block_Search(indexElem index[],int k,int n,int arr[]){
    int i = 0;
    int j,k;
    //寻找第一个块内最大关键字 >= k 的块 
    while((i < n) && index[i].key < k)
        i++;
    if(i >= n){
        printf("\nNot found");
        return 0;
    }
    //从块内查找
    j = index[i].low;
    while((j <= index[i].high) && arr[j] != k)
        j++;
    //查找越界
    if(j > index[i].high)
        printf("\nNot found");
    else
        return j;
}

二叉排序树

BST树的查找（类比一下二分查找）

思想：

首先将给定的k值与二叉排序树的根结点的关键字进行比较，若相等，则查找成功；

① 给定的k值小时BST的根结点的关键字，继续在该结点的左子树上进行查找；

② 给定的k值大于BST的根结点的关键字，继续在该结点的右子树上进行查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct BTNode{
    int key;
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode;

BTNode *research(BTNode *t,int k){
    if(t == NULL)			//1.递归结束条件
        return NULL;
    else{
        if(t->key == k)		//2.解决本次步骤
            return t;
        else if(k < t->key)	//3.递归转移方程
            return research(t->lchild, k);
        else
            return research(t->rchild, k);
    }
}

插入关键字算法

在插入过程中如果待插入关键字已经存在，则返回0，代表插入不成功；

如果待插入关键字不存在，则插入，并返回1，代表插入成功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Insert(BTNode *t,int key){
    //t为当前查找的结点（可能是根结点也可能不是）
    if(t == NULL){
        t = new BTNode;		//创建一个新结点（c++语法）
        t->key = key;
        t->lchild = t->rchild = NULL;
        return 1;
    }
    else{
       //查找成功不需要插入
        if(key == t->key)
            return 0; 
        //key 值小于当前结点，在左子树插入
        else if(key < t->key)
            return Insert(t->lchild, key);
        //key 值大于当前结点，在右子树插入
        else
            return Insert(t->rchild, key);
    }
}

二叉排序树的构造算法

1
2
3
4
5
//建立一个空树,每个数据元素都用插入算法插入
void Create(BTNode *t,int arr[],int n){
    for(int i = 0; i < n; i++)
        Insert(t,arr[i]);
}