Search Algorithms

1.循序搜尋法(sequential searching)

   又稱線性搜尋法(linear search)，為一筆一筆資料依序比對，直到找到所要搜尋的記錄為止。

   時間複雜度為O(n)

   平均搜尋長度= ( 1 + 2 +3 + ...... + n ) / n = ( n + 1 ) / 2

Example

int seqsearch(int a[], const int key, const int n){

    int i;

    for(i = 0 ; i < n ; i++)

        if(a[i] == key) return i;

    return -1;

}

2.二元搜尋法(binary searching)

   取中間值與搜尋值比對

   時間複雜度為O(log2n)

  差的情況下， n / 2 ^ m = 1 ，m = log2n，n個串列，m次比對。

   須事先予以排序

   中間值：mid = ( low + high ) / 2

Example 

//a[] is an sorted integer array

int binarysearch(int a [], const int x, const int n){

    int left = 0, right = n - 1;

    while (left <= right){

        int middle = (left + right) / 2;

        if(x > a[middle]) left = middle + 1;

        else if(x < a[middle]) right = middle - 1;

        else return middle;

     }

     return -1;

}