《圖說演算法-使用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); }
    }