# [資料結構] CH12. Searching
* 搜尋(Searching)指給予一個值，回傳該值在一個陣列中的哪個位置(或是不存在)。
* 在這裡會介紹幾種方法，每種方法都有不同的限制與效率。
* 正常來說我們會分析每種演算法的Big-Oh來定義效率，但這被歸類在演算法的課程，因此在此我們不討論，有興趣者請自行google。

## Linear Search
* 線性搜尋，簡單來講就是一個一個找。

int LinearSearch(int arr[],int size,int value)
{
    for(int i = 0; i < size; i++)
    {
        if(arr[i] == value) return i;
    }
    return -1;
}

## Binary Search
* 二分搜尋，只能用於**排序過**的陣列。
* 概念是不停地切半，就像猜數字遊戲(終極密碼)時，想快速結束遊戲的人會一直猜中間數字一樣。
* 每次都檢查`begin`和`end`的中間值`M`。
* 如果`M`=`value`，回傳`M`的位置。
* 如果`M`<`value`，將`end`改為`M-1`，並遞迴該副程式。
* 如果`M`>`value`，將`end`改為`M+1`，並遞迴該副程式。
* 如果`end`比`begin`小，代表找不到該數字。

## Interpolation Search
* 比例搜尋，Binary Search的強化版，一樣只能用於**排序過**的陣列。
* 概念是每次找的時候不再是對半切，而是根據**最大值**、**最小值**和**目標數字**來得到比例關係，藉此更精準的猜測下一次的位置。
* 利用的就是相似三角形的概念。
* 已知：min和max的陣列索引和值、目標值；需求：目標的索引。
* 如下圖。
* 寫成公式：`index=min+(max-min)*((value-a[min])/(a[max]-value))`
* 因為陣列可能值很極端(ex:1,2,3,4,5,50000)，比例算出來的不一定就是該值，還是需要再次檢查，照比例去找只是為了加速。
* 若該陣列中的數是等差數列，就可以很精準地找到。

## Jump Search
* 跳躍搜尋，有點像是Linear Search的強化版，但它需要**排序過**的陣列才可使用。
* 概念是不要一次一個一個找，而是先分群，找到目標在哪個群之後再對該群用Linear Search。
* 若陣列有`n`個數，我們分為$\sqrt{n}$群。

int JumpSearch(int arr[],int size,int value)
{
    int step = sqrt(size);
    for(int i = step - 1; i < size; i += step)
    {
        if(arr[i] == value) return i;
        else if(arr[i] > value) return LinearSearch(arr + i, step, value);
    }
    return -1;
}

###### tags: `DS` `note`