《圖說演算法-使用C#》要點摘錄 – 「搜尋演算法」

書名：《圖說演算法-使用C#》

作者：吳燦銘、胡昭民

所讀版本：博碩文化

搜尋方法

• 基於資料量大小：
  • 資料量大：外部搜尋
  • 資料量小：內部搜尋
• 基於被搜尋的數據是否異動：
  • 否：靜態搜尋
  • 是：動態搜尋

搜尋算法

線性搜尋法

• 從頭到尾搜索全部數據
• 優點：搜索前不對資料作任何處理
• 缺點：搜尋速度較慢
• 時間複雜度：
  • 如果數據沒有重覆，找到數據可中止搜索，最差情況為O(n)
  • 平均情況，數據出現機率相等，需進行(n+1)/2次比較
  • 數據量很大是不適合用線性搜尋
• 線性搜尋

public static bool SequentialSearch(int[] arr, int target)
{
    foreach (int item in arr)
    {
    	if(item == target) { return true; }
    }
    return false;
}

二分搜尋法

• 搜尋對象需要事先排序好，而且數據量必須能直接在記憶體中執行。
• 適用於靜態數據
• 將數據分割成兩等份，比較目標值和中間值的大小：
  • 目標值>中間值：目標值在右邊
  • 目標值<中間值：目標值在左邊
  • 目標值==中間值：找到目標值
• 時間複雜度：每次搜尋都會比上次少一半的範圍 -> O(log n)
• 二分查找

  •   public static int BinarySearch(int[] arr, int target)
      {
          int left = 0;
          int right = arr.Length - 1;
          int mid = 0;
      
          while(left <= right)
          {
              mid = (right - left) / 2 + left;
              if(arr[mid] == target) { return mid; }
              else if(arr[mid] < target)
              {
                  left = mid + 1;
              }
              else
              {
                  right = mid - 1;
              }
          }
          return -1;
      }

內插搜尋法

• 依照數據位置的分布，利用公式預測數據的所在位置，再以二分法的方式漸漸逼近。
• 內插法假設數據平均分布在陣列中，而每一筆數據的差距相當接近/有一定比例的距離
  • 內插法公式：mid = left + ((target - arr[left]) / (arr[right] - arr[left])) * (right - left)
• 時間複雜度：平均而言優於O(log n)
• 須先排序數據
• 內插搜尋

public static int InterpolationSearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;
    int interpolate = 0;
    while(left <= right && interpolate != -1)
    {
        interpolate = (int)((float)(target - arr[left]) * (right - left) / (arr[right] - arr[left]));
        int mid = left + interpolate;

        if(mid > right + 1 || mid < -1) { return -1; }
        else if(interpolate > arr[left] && interpolate > arr[right]) { return -1; }

        if(arr[mid] == target)
        {
        	return mid;
        }
        else if (arr[mid] < target)
        {
        	left = mid + 1;
        }
        else
        {
        	right = mid - 1;
        }
    }
    return -1;
}        

費氏搜尋法

• 以費氏級數分割數據，比二分法好的是只用到加減法而不需用到乘除法

• 費氏搜尋樹

  • 左右子樹均為費氏樹
  • 根節點(k)的費氏級數基於數據數量(n)決定：F(k + 1) >= n+1
  • 子節點與父節點的差值絕對值為費氏數
  • 當k >= 2
    • 費氏樹的樹根為Fib(k)
    • 左子樹為(k - 1)階費氏樹（樹根為Fib(k - 1)）
    • 右子樹為數(k - 2)階費氏樹（樹根為Fib(k) + Fib(k - 2)）
  • 若n + 1 != 費氏數的值，則找出存在一個m 使用 Fib(k + 1) - m = n + 1，m = Fib(k + 1) - (n + 1)，再依費氏樹的建立原則完成費氏樹的建立，最後將樹的各節點減去m，把值<1的節點去掉。

• target取值範圍

  • target < Fib(k) => target在1 到 Fib(k) - 1之間
  • target == Fib(k) => 找到數據
  • target > Fib(k) => target在 Fib(k) + 1 到 Fib(k+1) - 1之間

• 時間複雜度：

  • 平均情況：O(log2N)
  • 最壞情況比二分查找慢

• 算法複雜，需額外產生費氏樹

• 費氏搜尋

  •   public static int Fib_Search(int[] arr, int target)
      {
          //F(根節點 + 1) = 數組元素數量 + 1
          int idx = 2;
          while (Fib(idx) <= arr.Length) { idx++; }
          idx--;
      
          int rootNode = Fib(idx); //定義根節點
          int diff1 = Fib(idx - 1); //上一個費氏數
          int diff2 = rootNode - diff1; //上二個費氏數
          rootNode--;
      
          while (true)
          {
              if (target == arr[rootNode]) { return rootNode; }
              else
              {
                  if (idx == 2) { return arr.Length; }
                  if (target < arr[rootNode])
                  {
                      rootNode = rootNode - diff2;
                      int temp = diff1;
                      diff1 = diff2;
                      diff2 = temp - diff2;
                      idx = idx - 1;
                  }
                  else
                  {
                      if (idx == 3) { return arr.Length; }
                      rootNode = rootNode + diff2;
                      diff1 = diff1 - diff2;
                      diff2 = diff2 - diff1;
                      idx = idx - 2;
                  }
              }
          }
      }
      static int Fib(int n)
      {
          if (n == 1 || n == 0) { return n; }
          else { return Fib(n - 1) + Fib(n - 2); }
      }