查找算法复习——线性表的查找

    在复习数据结构的时候，我对查找也算学得比较好的，但是今天复习这块知识的时候，发现是那么的陌生，不知道是用的少，还是什么原因，这个时候，要是我当时能够写博客把那些东西总结一下，是不是效果会好些的，所以我要坚持写博客。

    查找分为两类——比较式的查找和计算式的查找。比较式的查找又分为线性查找法和基于树的查找法；而计算式的查找法就是哈希查找了。

    线性表的查找：

    1）顺序查找法。对于这种查找，就是一个一个挨着比较，如果找到了就成功，否则是失败的，再次不多说。

    2）折半查找法。也是二分搜索，它主要用的是分治法思想进行设计的。

问题描述：给定已经从小到大排好序的n个元素a[0]——a[n-1]，现在要在这n个元素当中找到一个特定的元素x。

算法分析：首先取a[n/2]与x比较，如果x==a[n/2]，则找到x，算法终止；如果xa[n/2]，则在后半部分进行查找。

具体程序实现：

/*binsearch_recursion.c*/
#include <stdio.h>

#define N 10

int binsearch(int left, int right, int x, int *a)
{
    int mid = (left+right)/2;
    int result;

    if(left > right) {
        result = -1;
        return result;
    }
    if(x == a[mid]) {
        result = mid;
    } else if(x < a[mid]) {
        result = binsearch(left, mid-1, x, a);
    } else {
        result = binsearch(mid+1, right, x, a);
    }
    return result;
}

int main()
{
    int a[N] = {12, 18, 23, 87, 98, 100, 120, 130, 155, 198};
    int x = 195, result;

    result = binsearch(0, N-1, x, a);
    if(result == -1) {
        printf("not found\n");
        return 0;
    }
    printf("The result is:a[%d]=%d\n", result, a[result]);
    return 0;
}

    这种实现是递归形式的，如果把它改为非递归形式如下：

/*binsearch.c*/
#include <stdio.h>

#define N 10

int binsearch(int left, int right, int x, int *a)
{
    int result, mid;

    while(left <= right) {
        mid = (left+right)/2;
        if(x == a[mid]) {
            result = mid;
            break;
        } else if(x > a[mid]) {
            left = mid+1;
        } else {
            right = mid-1;
        }
    }
    if(left > right) {
        result = -1;
    }
    return result;
}

int main()
{
    int a[N] = {12, 18, 23, 87, 98, 100, 120, 130, 155, 198};
    int x = 195, result;

    result = binsearch(0, N-1, x, a);
    if(result == -1) {
        printf("not found\n");
        return 0;
    }
    printf("The result is:a[%d]=%d\n", result, a[result]);
    return 0;
}

    3）分块查找法。对于这个查找算法我只是了解了思想：把表分成若干个块，之后建立一张索引表，这个索引表中的每一项记录每一块的最大元素值和每一块开始的下表。查找的时候，首先在索引表中根据折半查找或者顺序查找找到所对应的那个块，然后针对那一块进行查找。