8月 07, 2008

【演算】二分搜尋法 - Binary Search

@
  二分搜尋法(binary search)用以搜尋已排序的一串資料。其原理為將欲搜尋的值,與所有資料的中間值(中位數)做比對。

  假設在資料由小排到大的情況,若是搜尋值與中間值不同,且搜尋值比中間值為大。由於資料經過排序,我們可以得知:中間值以前的資料全都比搜尋值還小,所以我們就不需要再浪費時間搜尋這個範圍的值。

  相反的,若是搜尋值比中間值為小,我們也可以得知:中間值以後的資料全都比搜尋值還大,也代表接下來我們不需要去尋找中間值以後的值。

  接著,由於搜尋到資料的可能範圍僅剩下一半(中間值之前或之後)。我們運用同樣的方式,取出這個範圍資料的中間值與搜尋值做比對。再依據此中間值將資料分成兩半,直到找到搜尋值為止。


  舉例來說,現在我們需要在下面這些資料中搜尋數值 44:

3 7 14 20 23 32 41 44 56 57 73 89 93

  由於中間值 41 小於搜尋值 44。因此我們可以知道,在 41 之前的資料皆小於搜尋值 44。

3 7 14 20 23 32 41 44 56 57 73 89 93

  接著,由於 41 之後資料中的中間值 57 大於搜尋值 44。我們可以知道,在 57 之前的資料皆大於搜尋值 44。

3 7 14 20 23 32 41 44 56 57 73 89 93

  接著我們將 41 與 57 之間的中間值與搜尋值比對。發現中間值 44 等於搜尋值,這次就找到欲尋找的值了。


  二分搜尋的虛擬碼大致如下:

void binarysearch(Type data[1..n], Type search)
{
    Index low = 1;
    Index high = n;

    while (low <= high)
    {
        Index mid = (low + high) / 2;

        if (data[mid] = search)
        {
            print mid;
            return;
        }
        else if (data[mid] > search)
        {
            high = mid - 1;
        }
        else if (data[mid] < search)
        {
            low = mid + 1;
        }
    }

    print "Not found";
}


  若是有 n 筆資料,在最差的情況下,二分搜尋法總共需要比較 [log2n] + 1 次。

  顯然的,此種搜尋法較循序搜尋法(linear search)快速許多。


  以 C 語言的實作如下:

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

int binarysearch(int[], int, int);

int main(void)
{
    int search, ans;
    int data[] = {3, 7, 14, 20, 23, 32, 41, 44, 56, 57, 73, 89, 93};

    printf("請輸入欲搜尋的資料: ");
    scanf("%d", &search);

    // 呼叫函式進行搜尋
    ans = binarysearch(data, search, sizeof(data) / sizeof(int));

    if (ans < 0)
    {
        printf("找不到 %d\n", search);
    }
    else
    {
        printf("在第 %d 筆資料找到 %d\n", ans + 1, search);
    }

    system("pause");
}

int binarysearch(int data[], int search, int n)
{
    int low = 0, high = n - 1;

    while (low <= high)
    {
        int mid = (low + high) / 2;

        if (data[mid] == search)
        {
            return mid;
        }
        else if (data[mid] > search)
        {
            high = mid - 1;
        }
        else if (data[mid] < search)
        {
            low = mid + 1;
        }
    }

    return -1;
}

9 回覆:

阿強 提到...

你這個程式碼真的寫得很好
可是有個缺點!! 就是不能用COPY的有點麻煩ㄟ
請你改善3Q 我們會再看一次謝謝

小參 提到...

您好,請問"不能用copy的"指的是什麼呢?

匿名 提到...

他應該是懶的打,想直接copy你的程式到編譯器中compile

小強,動動個手吧...

小參 提到...

原來如此, 我瞭解了

我猜阿強用的大概是 IE 核心的瀏覽器
所以導致無法直接選取複製吧
假如想要直接複製, 可以改用其他瀏覽器再試看看喔

大船 提到...

有个问题哦。
mid = (low + high) / 2,此时low + high是可能超出int的最大值哦,那么这时mid值已经异常,再用data[mid]已经越界访问了,程序会直接down掉。
应该改成 mid = low + (high - low) / 2;可避免溢出问题。
还有个地方,就是如果输入数据中有多个数值相同,那么返回的索引并不是第一个数值的哦。这在某些应用下也可能会造成问题。

C.E.W. 提到...

您好,這個範例為了簡單起見,當初並沒有考慮到您所提到的問題。
我會再對內文進行修正,感謝您的提醒。

Chris 提到...

您好,您的資料真是完整,請問可以再放用遞迴的寫法嗎?

匿名 提到...

我想請問
那如果是在17,26,44,56,88,97中找尋26
那麼一開始的中間值是哪個數字?

匿名 提到...

整數除法(0+5)/2=2
data[2]為44

張貼留言