書籍資訊
- 書名：
《圖解演算法：使用 C#》 - 類型：演算法與搜尋方法整理
這篇在講什麼
這一篇是在整理幾種常見搜尋法，重點不是列舉公式，而是先判斷：
- 資料有沒有排序
- 資料量大不大
- 資料分布是否均勻
不同前提下，適合的搜尋法會完全不同。
搜尋前的基本分類
在挑搜尋法前，先問三件事：
- 資料有沒有先排好序
- 要不要支援頻繁更新
- 搜尋成本能不能換取前置處理成本
如果資料沒有排序，很多高效率搜尋法都用不上。
如果資料會一直改動，維持排序本身也有成本。
線性搜尋
線性搜尋最直接：
- 從頭找到尾
- 看到目標就停
它的優點是：
- 不需要排序
- 實作最簡單
- 任何可遍歷資料都能用
缺點也很明顯：
- 平均和最差通常是
O(n) - 資料量大時效率不理想
public static bool LinearSearch(int[] nums, int target)
{
foreach (int num in nums)
{
if (num == target)
{
return true;
}
}
return false;
}二分搜尋
二分搜尋的前提很重要：
- 資料必須已排序
做法是每次看中間值，再決定往左半還是右半繼續找。
因為每次都砍掉一半範圍，所以時間複雜度是 O(log n)。
public static int BinarySearch(int[] nums, int target)
{
int left = 0;
int right = nums.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target)
{
return mid;
}
if (nums[mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return -1;
}插值搜尋
插值搜尋可以看成是「會猜位置」的二分搜尋。
它不是每次都切正中間，而是根據數值分布去估計 target 比較可能落在哪裡。
所以它比較適合：
- 資料已排序
- 數值分布相對均勻
如果分布很不平均，它的表現就未必比二分搜尋好。
費波那契搜尋
費波那契搜尋同樣屬於有序資料上的搜尋法，只是切分方式改成利用費波那契數列。
它的思路可以理解成：
- 不用每次取正中間
- 而是依照費波那契比例來縮小區間
這類方法比較偏演算法教材中的經典技巧，實務上最常見的主力仍然是二分搜尋。
我自己的整理
如果今天只是要快速做選擇，我會先這樣想：
- 沒排序：先線性搜尋
- 已排序：先二分搜尋
- 已排序且分布均勻：才考慮插值搜尋
- 想理解經典技巧：再看費波那契搜尋
換句話說，搜尋法不是越複雜越好，而是越符合前提越好。
先記住的重點
- 二分搜尋的最大前提是資料已排序
- 線性搜尋雖慢，但通用性最高
- 插值搜尋吃資料分布，條件不對時不一定划算
- 費波那契搜尋是經典方法，但實務主力通常仍是二分搜尋
- 搜尋效率常常不是只看搜尋本身，還要把前置排序成本一起算進去