查找的几种常见方法

这是电子科技大学软件技术基础课程的练习题,源码在 Github 上有,需要的话取用,最好能注明出处,谢谢。


顺序查找

//  Created by Toxni on 12/28/15.
//  Copyright © 2015 Toxni. All rights reserved.

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

int ordersearch(int a[], int n, int des){  
    int i;
    for(i=0; i<n; i++)
        if(des==a[i])
            return 1;
    return 0;
}

int main(){  
    int i, val;
    int a[] = {3, 10, 13, 17, 40, 45, 50, 70};
    int ret;

    for (i=0; i<8; i++)
        printf("%d\t", a[i]);

    printf("\nplease input the aim: ");

    while (1){
        scanf("%d", &val);

        if (val == -1) {
            break;
        }

        ret = ordersearch(a, 8, val);

        if(1 == ret)
            printf ("found it");
        else
            printf ("do not exist");

        printf("\nplease input the aim, input -1 to stop: ");

    }

    return 0;
}


二分法查找

//  Created by Toxni on 12/28/15.
//  Copyright © 2015 Toxni. All rights reserved.

#include <stdio.h>

int binarySearch(int a[], int n, int key){  
    int low = 0;
    int high = n - 1;
    while(low<= high){
        int mid = (low + high)/2;
        int midVal = a[mid];
        if(midVal<key)
            low = mid + 1;
        else if(midVal>key)
            high = mid - 1;
        else
            return mid;
    }
    return -1;
}

int main(){  
    int i, val, ret;
    int a[8]={3, 10, 13, 17, 40, 45, 50, 70};
    for(i=0; i<8; i++)
        printf("%d\t", a[i]);

    printf("\nplease input the aim: ");


    while (1){
        scanf("%d",&val);
        if (val == -1) {
            break;
        }

        ret = binarySearch(a,8,val);

        if (-1 == ret)
            printf("do not exist\n");
        else
            printf("found it\n");

        printf("\nplease input the aim, input -1 to stop: ");
    }
        return 0;
}