查找

順序表查找

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

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é)們會疑惑為什么 “i” 從 “1” 開始遍歷，因為 “0” 我們要做錯誤輸出呀。。。

那么我們根據(jù)這個算法我們給他稍微的改進(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” 代表查找失敗，但是這樣寫的好處什么是呢？好處就是我不用瘋狂的去判斷 “i < n” ，看官們想明白了么？

有序表的查找

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

二分查找（折半查找）

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

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

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

差值查找

差值查找這個東西呢，按照我的理解就是一個不規(guī)范的二分查找?；蛘哒f二分查找是一個特殊的差值查找。我們怎么理解這個差值查找呢？看官不要急？我先把差值查找的公式給大家列一下

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

然后很多人會大罵一句，我曹，什么鬼。那是因為我markdown用的不熟，其實是我懶得去查數(shù)學(xué)公式怎么列，哈哈。

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

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