查找

順序表查找

順序表查找的算法大家公認(rèn)的最簡(jiǎn)單的就是下面這種查找了，我想只要寫(xiě)過(guò)代碼的應(yīng)該都知道怎么寫(xiě)了 哈哈哈

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;
}

同學(xué)們會(huì)疑惑為什么 “i” 從 “1” 開(kāi)始遍歷，因?yàn)?“0” 我們要做錯(cuò)誤輸出呀。。。

那么我們根據(jù)這個(gè)算法我們給他稍微的改進(jìn)一下，看官們看好了。

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

這里一樣的 “0” 代表查找失敗，但是這樣寫(xiě)的好處什么是呢？好處就是我不用瘋狂的去判斷 “i < n” ，看官們想明白了么？

有序表的查找

順序表的查找看完了之后，看官們就可以隨我看看有序表的查找。所謂的有序表，就是有大小的順序，我們下面的有序表默認(rèn)的都是按照從大到小排序的，如果各位看官覺(jué)得排序算法還是需要給大家科普一下的話(huà)，那么出門(mén)請(qǐng)右轉(zhuǎn)。

二分查找（折半查找）

但是我看到這個(gè)折半查找的時(shí)候就覺(jué)得特別的蛋疼，好好地二分非要教程折半查找，真是呵呵噠。

所謂二分查找么，顧名思義了，每次都取中間的數(shù)據(jù)來(lái)查找看看對(duì)不對(duì)嘛。各位有想過(guò)跟順序表查找的遍歷有什么好處呢？

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

差值查找

差值查找這個(gè)東西呢，按照我的理解就是一個(gè)不規(guī)范的二分查找。或者說(shuō)二分查找是一個(gè)特殊的差值查找。我們?cè)趺蠢斫膺@個(gè)差值查找呢？看官不要急？我先把差值查找的公式給大家列一下

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

然后很多人會(huì)大罵一句，我曹，什么鬼。那是因?yàn)槲襪arkdown用的不熟，其實(shí)是我懶得去查數(shù)學(xué)公式怎么列，哈哈。

實(shí)際上，我們看前面的 二分查找的公式，是不是可以改寫(xiě)成這樣

mid = low + 1 / 2 *（high - low）