代码解析 折半查找 二叉搜索树

问题 A: 折半查找的次数

题目描述 给你一个无重复数的有序序列，如果采用折半查找的方式，对于给定的数，需要比较几次找到，请编程实现。

因为题目中给我们的数据已经是有序的序列，而且题目中明确告诉了我们，我们用二分查找法即可。二分查找就是：我们最开始定义一个左范围l和右范围r，如果我们查找的这个元素刚好是当前范围中间的那个mid说明已经找到，如果mid所在位置的元素>我们要找的元素，说明我们应该在左边的范围（元素都小于中间元素）继续查找，否则就在右边的范围查找

如何终止循环？

因为我们一直在缩小范围，最后结束的条件就是l>=r，只要l<r我们就可以继续查找

如何判断无法找到？

我们定义一个状态变量flag，如果flag是true就表明我们已经找到元素了，如果整个范围都找完了之后，flag仍然为false就表明没有找到元素

代码

#include<cstdio>
using namespace std;
int a[1005];
int main() {
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    scanf("%d",&x);
    int l=1,r=n,mid;
    int ans=0;
    bool flag=false;
    while(l<r) {
        mid = (l+r)>>1;
        if(a[mid]==x) {
            flag=true;
            ans++;
            break;
        }
        if(x>a[mid]) {
            l = mid + 1;
        }
        else {
            r = mid;
        }
        ans++;
    }
    if(!flag) printf("NO");
    else printf("%d",ans);
    return 0;
}

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
27
28
29
30
31
32
33

问题 B: 二叉搜索树中的查找
题目描述
给你一个数据序列，请构造一个二叉搜索树，然后计算出找到给定数据需比较的次数。

什么是二叉搜索树？

二叉搜索树是这样一颗二叉树：每一个结点左边的结点都小于当前结点，每一个结点右边的结点都大于当前结点

如何构造二叉搜索树？

最开始是一颗空树的时候，我们新建一个结点，存储第一个结点，之后插入结点的时候，我们最开始跟第一个结点比较大小，如果比第一个结点大，并且第一个结点没有右子树的话，我们就新建一个当前结点（最开始左子树和右子树都赋值为-1，表明没有左右子树），并且把第一个结点的右子树存储新建结点的编号，如果比第一个结点小，如果没有左子树，就新建结点当作左子树，如果有左子树的话，那么当前结点就跟这颗左子树相互比较，一直比较到一个可以插入的位置为止

如果有重复元素怎么办？

如果有重复元素的话，我们在构造二叉搜索树的时候，如果找到了当前元素的值，我们就可以不插入这个结点，直接返回

如何查找？

就从第一个元素开始查找咯，如果比当前结点要大的话，就继续查找这个结点的右子树，小的话就查找左子树，如果一直查找完了都没找到就是没有
代码
cnt表明我们当前这颗二叉搜索树的结点个数，cur表明当前是哪个结点，insert（x）是在树插入x这个元素，find（x）是在树中查找元素x，如果没有找到就返回-1，这里退出循环的条件有两个，一个是结点已经大于树的结点数了，第二个条件是我们已经找到最底部的-1了还是没有找到，那么就退出

#include<cstdio>
using namespace std;
struct node {
    int data,l,r;
}e[1005];
int cnt=0;
void insert(int x) {
    if(!cnt) {
        e[++cnt].data=x;
        e[cnt].l=-1;
        e[cnt].r=-1;
        return;
    }
    int cur=1;
    while(cur<=cnt) {
        if(x==e[cur].data) {
            break;
        }
        if(x>e[cur].data) {
            if(e[cur].r==-1) {
                e[++cnt].data=x;
                e[cnt].l=-1;
                e[cnt].r=-1;
                e[cur].r = cnt;
                break;
            }
            else cur = e[cur].r;
        }
        else {
            if(e[cur].l==-1) {
                e[++cnt].data=x;
                e[cnt].l=-1;
                e[cnt].r=-1;
                e[cur].l = cnt;
                break;
            }
            else cur = e[cur].l;
        }
    }
}
int find(int x) {
    int cur=1;
    int ans=0;
    while(cur<=cnt&&cur!=-1) {
        ans++;
        if(e[cur].data==x) {
            return ans;
        }
        if(e[cur].data>x) {
            cur = e[cur].l;
        }
        else {
            cur = e[cur].r;
        }
    }
    return -1;
}
int main() {
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        insert(x);
    }
    scanf("%d",&x);
    int ans = find(x);
    if(ans==-1) printf("NO");
    else printf("%d",ans);
    return 0;
}


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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72