欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

查找

程序员文章站 2022-07-12 09:10:48
...

查找

顺序表查找

顺序表查找的算法大家公认的最简单的就是下面这种查找了,我想只要写过代码的应该都知道怎么写了 哈哈哈

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

同学们会疑惑为什么 “i” 从 “1” 开始遍历,因为 “0” 我们要做错误输出呀。。。

那么我们根据这个算法我们给他稍微的改进一下,看官们看好了。

int Sequential_Search2(int *a, int n, int key) {
    int i;
    a[0] = key;
    i = n;
    while(a[i] != key) {
        i --;
    }
    return i;
}

这里一样的 “0” 代表查找失败,但是这样写的好处什么是呢?好处就是我不用疯狂的去判断 “i < n” ,看官们想明白了么?

有序表的查找

顺序表的查找看完了之后,看官们就可以随我看看有序表的查找。所谓的有序表,就是有大小的顺序,我们下面的有序表默认的都是按照从大到小排序的,如果各位看官觉得排序算法还是需要给大家科普一下的话,那么出门请右转。

二分查找(折半查找)

但是我看到这个折半查找的时候就觉得特别的蛋疼,好好地二分非要教程折半查找,真是呵呵哒。

所谓二分查找么,顾名思义了,每次都取中间的数据来查找看看对不对嘛。各位有想过跟顺序表查找的遍历有什么好处呢?

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

二分查找的中值公式是什么呢?

mid = (low + high) / 2

差值查找

差值查找这个东西呢,按照我的理解就是一个不规范的二分查找。或者说二分查找是一个特殊的差值查找。我们怎么理解这个差值查找呢?看官不要急?我先把差值查找的公式给大家列一下

mid = low + (key - a[low]) / (a[high] - a[low]) * (high - low)

然后很多人会大骂一句,我曹,什么鬼。那是因为我markdown用的不熟,其实是我懒得去查数学公式怎么列,哈哈。

实际上,我们看前面的 二分查找的公式,是不是可以改写成这样

mid = low + 1 / 2 *(high - low)