3.1 - Searching

介紹Linear Search和Binary Search

1. Linear Search(Sequencial Search)

從頭到尾一一比較每一筆資料直到找到目標或是搜尋完範圍仍找不到為止。

1. 資料不需事先排序過

2. 資料可存放於Linklist(Sequencial Access)或是Array(Random Access)

3. 時間複雜度: O(n) （平均比較次數 $=\frac{1+2+..+n}{n}$ ）

4. 適合資料少使用

2. Binary Search

1. 資料必須事先由小到大排序過

2. 資料必須使用Array儲存

2.1 Iterative

int BinarySearch(char *str, char key){
    int high = strlen(str);
    int low = 0;
    int mid;
    while(low <= high){
        mid = (low + high)/2;
        if (key == str[mid]) return mid;
        if (key > str[mid]) low = mid + 1;
        if (key < str[mid]) high = mid - 1;
    }
    return -1; //not found
}

2.2 Recursive

int BinarySearch(char *str, char key, int high, int low){
    int mid = (low + high)/2;
    if (key == str[mid]) return mid;
    if (key > str[mid]) return BinarySearch(str, key, high, mid + 1);
    if (key < str[mid]) return BinarySearch(str, key, mid - 1, low);
    return -1;
}

時間複雜度分析:

$T(n)=1+T(\frac{n}{2})\\ \quad\quad\ =1+(1+T(\frac{n}{4}))\\ \quad\quad\ =2+(1+T(\frac{n}{8}))...\\ \quad\quad\ =\log n+T(1)$

Time = O(logn)