【演算】二分搜尋法 - 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 筆資料，在最差的情況下，二分搜尋法總共需要比較 [log₂n] + 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;
}