读书笔记: 查找和验证 Search and Verify

1
2

#include <stdio.h>
#define COMPARE(x,y) ((x)>(y) ? 1 : ((x) == (y)) ? 0 : -1)

Seqsearch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//O(n)
int seqsearch(int list[],int n,int searchnum){
    int i;
    list[n]=searchnum;  //内存会溢出么？
    for(i=0;list[i]!=searchnum;i++)
        ;
    return ((i<n)?i:-1);
}

int my_seqsearch(int list[],int n,int searchnum){
    int i;
    for(i=0;i<n;i++){
        if(list[i]==searchnum) return i;
    }
    return -1;
}

Binsearch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//O(log n)
int binsearch(int list[],int n,int searchnum){
    int left,right,middle;
    left = 0;
    right = n-1;
    
    while(left<=right){
        middle = (left + right) / 2;
        switch(COMPARE(list[middle],searchnum)){
            case 1:
                right = middle - 1;
                break;
            case 0:
                return middle;
                break;
            case -1:
                left = middle + 1;
                break;
        }
    }
    return -1;
}

Verify

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

//顺序查找进行表验证O(mn)
#define MAX_SIZE 1024
void verify1(int list1[],int list2[],int n,int m){
    int i,j;
    int marked[MAX_SIZE];
    
    for(i=0;i<m;i++){
        marked[i] = 0;
    }
    for(i=0;i<n;i++){
        if((j=seqsearch(list2,m, list1[i]) < 0))
            printf("%d is not in list 2 \n",list1[i]);
        else
            marked[j]=1;
    }
    for(i=0;i<m;i++){
        if(marked[i]==0){
            printf("%d is not in list1 \n",list2[i]);
        }
    }
}

//两个表的快速验证
//O(tsort(n)+tsort(m)+m+n),假如sort()为O(nlogn)，则最终O(max[nlogn,mlogm])
void verify2(int list1[],int list2[],int n,int m){
    int i,j;
    sort(list1,n);
    sort(list2,n);
    i=j=0;
    while(i<n && j<m){
        if(list1[i] <list2[j]){
            printf("%d is not in list 2",list1[i]);
            i++;
        } else if (list1[i]==list2[j]){
            i++;j++;
        } else {
            printf("%d is not in list1 \n" ,list2[j]);
            j++;
        }
    }
    for(;i<n;i++){
        printf("%d is not in list 2 \n",list1[i]);
    }
    for(;j<n;j++){
        printf("%d is not in list 1 \n",list2[j]);
    }
}