Java實現常見查找演算法

来源:https://www.cnblogs.com/dupengpeng/archive/2023/09/13/17699995.html
-Advertisement-
Play Games

Java實現常見查找演算法 查找是在大量的信息中尋找一個特定的信息元素,在電腦應用中,查找是常用的基本運算,例如編譯程式中符號表的查找。 線性查找 線性查找(Linear Search)是一種簡單的查找演算法,用於在數據集中逐一比較每個元素,直到找到目標元素或搜索完整個數據集。它適用於任何類型的數據集 ...


Java實現常見查找演算法

查找是在大量的信息中尋找一個特定的信息元素,在電腦應用中,查找是常用的基本運算,例如編譯程式中符號表的查找。

線性查找

線性查找(Linear Search)是一種簡單的查找演算法,用於在數據集中逐一比較每個元素,直到找到目標元素或搜索完整個數據集。它適用於任何類型的數據集,無論是否有序,但在大型數據集上效率較低,因為它的時間複雜度是 O(n),其中 n 是數據集的大小。

以下是線性查找的基本步驟:

  1. 從數據集的第一個元素開始,逐一遍歷每個元素。
  2. 比較當前元素與目標元素是否相等。
    • 如果相等,表示找到了目標元素,返回當前元素的索引位置。
    • 如果不相等,繼續遍歷下一個元素。
  3. 如果遍歷完整個數據集都沒有找到目標元素,則返回一個表示元素不存在的標識(如 -1)。

以下是使用Java實現線性查找的示例代碼:

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // 目標元素的索引位置
            }
        }
        return -1; // 目標元素不存在於數組中
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;
        int result = linearSearch(arr, target);
        if (result == -1) {
            System.out.println("目標元素不存在於數組中");
        } else {
            System.out.println("目標元素的索引位置為: " + result);
        }
    }
}

二分查找

二分查找演算法(Binary Search)是一種高效的查找演算法,用於在有序數組或列表中查找特定元素的位置。它的基本思想是通過將數組分成兩半,然後確定目標元素在哪一半,然後繼續在那一半中搜索,重覆這個過程直到找到目標元素或確定不存在。

二分查找演算法的時間複雜度是 O(log n),其中 n 是數據集的大小。這使得它在大型有序數據集中的查找操作非常高效,每次將數據集分成兩半,然後確定目標元素在哪一半,然後繼續在那一半中搜索。每次操作都將數據集的規模減少一半,因此它的時間複雜度是對數級別的.

需要註意的是,二分查找演算法要求數據集必須是有序的如果數據集無序,需要先進行排序操作。排序操作通常具有較高的時間複雜度(如快速排序的平均時間複雜度為 O(n log n)),因此總體上二分查找演算法加上排序操作的時間複雜度可能會更高。

總結起來,二分查找演算法是一種高效且常用的查找演算法,在大型有序數據集中具有較低的時間複雜度。

以下是二分查找演算法的詳細步驟:

  1. 初始化左指針 left 為數組的起始位置,右指針 right 為數組的結束位置。
  2. 計算中間位置 mid,即 mid = left + (right - left) / 2
  3. 比較中間位置的元素與目標元素:
    • 如果中間位置的元素等於目標元素,則返回中間位置。
    • 如果中間位置的元素大於目標元素,則更新右指針 right = mid - 1,並回到步驟2。
      • 如果中間位置的元素小於目標元素,則更新左指針 left = mid + 1,並回到步驟2。
  4. 如果左指針大於右指針,則表示目標元素不存在於數組中。

以下是使用Java實現二分查找演算法的示例代碼(迭代法):

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;// 左指針,初始為數組起始位置
        int right = arr.length - 1;// 右指針,初始為數組結束位置
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // 計算中間位置
       
            if (arr[mid] == target) { // 如果中間位置的元素等於目標元素,則找到目標元素
                return mid;
            } else if (arr[mid] < target) { // 如果中間位置的元素小於目標元素,則在右半部分繼續查找
                left = mid + 1;
            } else {  // 如果中間位置的元素大於目標元素,則在左半部分繼續查找
                right = mid - 1;
            }
        }
        
        return -1; // 目標元素不存在於數組中

遞歸法

public class BinarySearchRecursive {
    public static int binarySearch(int[] arr, int target, int left, int right) {
        if (left <= right) {
            int mid = left + (right - left) / 2;// 計算中間位置

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {// 如果中間位置的元素小於目標元素,則在右半部分繼續查找
                return binarySearch(arr, target, mid + 1, right);
            } else {// 如果中間位置的元素大於目標元素,則在左半部分繼續查找
                return binarySearch(arr, target, left, mid - 1);
            }
        }

        return -1; // 目標元素不存在於數組中
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;
        int result = binarySearch(arr, target, 0, arr.length - 1);
        
        if (result == -1) {
            System.out.println("目標元素不存在於數組中");
        } else {
            System.out.println("目標元素的索引位置為: " + result);
        }
    }
}

如果數組中有多個相同的目標元素,上面的演算法只會返回其中一個的索引位置,可以優化一下返回全部元素的下標

// 迭代
public static List<Integer> binarySearchAllIterative(int[] arr, int target) {
    List<Integer> indices = new ArrayList<>();
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            indices.add(mid);

            // 向左掃描找到所有相同元素的索引
            int temp = mid - 1;
            while (temp >= 0 && arr[temp] == target) {
                indices.add(temp);
                temp--;
            }

            // 向右掃描找到所有相同元素的索引
            temp = mid + 1;
            while (temp < arr.length && arr[temp] == target) {
                indices.add(temp);
                temp++;
            }

            break; // 結束迴圈,避免重覆掃描
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return indices;
}

// 遞歸
public class BinarySearchMultiple {
    public static List<Integer> binarySearchAll(int[] arr, int target) {
        List<Integer> indices = new ArrayList<>();
        binarySearchAllRecursive(arr, target, 0, arr.length - 1, indices);
        return indices;
    }

    public static void binarySearchAllRecursive(int[] arr, int target, int left, int right, List<Integer> indices) {
        if (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                indices.add(mid); // 將找到的索引加入列表
                // 繼續在左半部分和右半部分繼續查找相同目標元素的索引
                binarySearchAllRecursive(arr, target, left, mid - 1, indices);
                binarySearchAllRecursive(arr, target, mid + 1, right, indices);
            } else if (arr[mid] < target) {
                binarySearchAllRecursive(arr, target, mid + 1, right, indices);
            } else {
                binarySearchAllRecursive(arr, target, left, mid - 1, indices);
            }
        }
    }
}

通常情況下,迭代法比遞歸法的效率要高。這是因為迭代法避免了函數調用的開銷,而函數調用涉及堆棧管理、參數傳遞等操作,會導致一定的性能損耗。此外,迭代法通常更容易優化,可以通過使用迴圈不斷更新變數的方式來進行計算,從而更有效地利用計算資源。

插值查找

插值查找演算法是一種基於有序數組的搜索演算法,類似於二分查找,但它在選擇比較的元素時使用了一種更為精細的估計方法,從而更接近目標元素的位置。插值查找的基本思想是根據目標元素的值與數組中元素的分佈情況,估算目標元素在數組中的大致位置,然後進行查找。

在二分查找中,mid的計算方式如下:

\[mid = \frac{low+high}{2} \]

將low從分數中提取出來,mid的計算就變成了:

\[mid =low + \frac{low+high}{2} \]

在插值查找中,mid的計算方式轉換成了:

\[mid =low + \frac{key-a[low] }{a[high] - a[low]}(high-low) \]

low 表示左邊索引left, high表示右邊索引right,key 就是target

插值查找演算法的步驟如下:

  1. 初始化左指針 left 為數組的起始位置,右指針 right 為數組的結束位置。
  2. 使用插值公式來估算目標元素的位置:
    pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left])
    其中,target 是目標元素的值,arr[left]arr[right] 分別是當前搜索範圍的左邊界和右邊界的元素值。
  3. 如果估算位置 pos 對應的元素值等於目標元素 target,則找到目標元素,返回位置 pos
  4. 如果估算位置 pos 對應的元素值小於目標元素 target,則說明目標元素在當前位置的右側,更新 left = pos + 1
  5. 如果估算位置 pos 對應的元素值大於目標元素 target,則說明目標元素在當前位置的左側,更新 right = pos - 1
  6. 重覆步驟 2 到步驟 5,直到找到目標元素或搜索範圍縮小到無法繼續搜索為止。

插值查找的優勢在於當數組元素分佈均勻且有序度較高時,其效率可以比二分查找更高。然而,當數組元素分佈不均勻或有序度較低時,插值查找可能會導致性能下降,甚至變得不如二分查找。

需要註意的是,插值查找演算法的時間複雜度通常為 O(log log n),但在某些特殊情況下,可能會退化為 O(n)。因此,在選擇搜索演算法時,需要根據具體的數據分佈情況和性能需求進行考慮。

插值查找演算法的示例代碼:

public class InterpolationSearch {
    /**
     * 插值查找演算法
     *
     * @param arr    有序數組
     * @param target 目標元素
     * @return 目標元素在數組中的索引位置,如果不存在則返回 -1
     */
    public static int interpolationSearch(int[] arr, int target) {
        int left = 0; // 左指針,初始為數組起始位置
        int right = arr.length - 1; // 右指針,初始為數組結束位置

        while (left <= right && target >= arr[left] && target <= arr[right]) {
            // 使用插值公式估算目標元素的位置
            int pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);

            if (arr[pos] == target) {
                return pos; // 找到目標元素
            }

            if (arr[pos] < target) {
                left = pos + 1; // 目標元素在右半部分
            } else {
                right = pos - 1; // 目標元素在左半部分
            }
        }
        return -1; // 目標元素不存在於數組中
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;
        int result = interpolationSearch(arr, target);
        if (result == -1) {
            System.out.println("目標元素不存在於數組中");
        } else {
            System.out.println("目標元素的索引位置為: " + result);
        }
    }
}

斐波那契查找

斐波那契查找是一種基於黃金分割原理的查找演算法,它是對二分查找的一種改進。斐波那契查找利用了斐波那契數列的特性來確定查找範圍的分割點,從而提高了查找效率。

隨著斐波那契數列的遞增,前後兩個數的比值會越來越接近0.618,利用這個特性,我們就可以將黃金比例運用到查找技術中,斐波那契查找原理與前兩種相似,僅僅改變了中間結點(mid)的位置,mid不再是中間或插值得到,而是位於黃金分割點附近,即mid=low+F(k-1)-1(F代表斐波那契數列)

斐波那契查找的基本思想如下:

  1. 首先,需要準備一個斐波那契數列,該數列滿足每個元素等於前兩個元素之和。例如:0, 1, 1, 2, 3, 5, 8, 13, ...

  2. 初始化左指針 left 和右指針 right 分別指向數組的起始位置和結束位置。

  3. 根據數組長度確定一個合適的斐波那契數列元素作為分割點 mid,使得 mid 儘可能接近數組長度。

  4. 比較目標元素與分割點mid

    對應位置的元素值:

    • 如果目標元素等於 arr[mid],則找到目標元素,返回位置 mid
    • 如果目標元素小於 arr[mid],則說明目標元素在當前位置的左側,更新右指針為 mid - 1
    • 如果目標元素大於 arr[mid],則說明目標元素在當前位置的右側,更新左指針為 mid + 1
  5. 重覆步驟 3 和步驟 4,直到找到目標元素或搜索範圍縮小到無法繼續搜索為止。、

斐波那契查找的優勢在於它能夠更快地確定分割點,從而減少了比較次數。它的時間複雜度為 O(log n),與二分查找相同。然而,斐波那契查找需要預先計算斐波那契數列,並且在每次查找時都需要重新確定分割點,因此在實際應用中可能會帶來一定的額外開銷。

需要註意的是,斐波那契查找適用於有序數組,並且數組長度較大時效果更好。對於小規模的數組或者無序數組,二分查找可能更適合。

代碼示例:

public class FibonacciSearch {

    public static int maxSize = 20;
    public static void main(String[] args) {
        int [] arr = {1,4, 10, 69, 1345, 6785};

        System.out.println("index=" + fibSearch(arr, 1345));// 0

    }

    // 生成 斐波那契數列
    public static int[] fib() {
        int[] f = new int[20];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    /**
     *
     * @param a  數組
     * @param key 我們需要查找的關鍵碼(值)
     * @return 返回對應的下標,如果沒有-1
     */
    public static int fibSearch(int[] a, int key) {
        int low = 0;
        int high = a.length - 1;
        int k = 0; //表示斐波那契分割數值的下標
        int mid = 0; //存放mid值
        int f[] = fib(); //獲取到斐波那契數列
        //獲取到斐波那契分割數值的下標
        while(high > f[k] - 1) {
            k++;
        }
        //因為 f[k] 值 可能大於 a 的 長度,因此我們需要使用Arrays類,構造一個新的數組,並指向temp[]
        //不足的部分會使用0填充
        int[] temp = Arrays.copyOf(a, f[k]);
        //實際上需求使用a數組最後的數填充 temp
        for(int i = high + 1; i < temp.length; i++) {
            temp[i] = a[high];
        }

        while (low <= high) { // 只要這個條件滿足,就可以找
            mid = low + f[k - 1] - 1;
            if(key < temp[mid]) { //我們應該繼續向數組的前面查找(左邊)
                high = mid - 1;
                //說明
                //1. 全部元素 = 前面的元素 + 後邊元素
                //2. f[k] = f[k-1] + f[k-2]
                //因為 前面有 f[k-1]個元素,所以可以繼續拆分 f[k-1] = f[k-2] + f[k-3]
                //即 在 f[k-1] 的前面繼續查找 k--
                //即下次迴圈 mid = f[k-1-1]-1
                k--;
            } else if ( key > temp[mid]) { // 我們應該繼續向數組的後面查找(右邊)
                low = mid + 1;
                //1. 全部元素 = 前面的元素 + 後邊元素
                //2. f[k] = f[k-1] + f[k-2]
                //3. 因為後面我們有f[k-2] 所以可以繼續拆分 f[k-1] = f[k-3] + f[k-4]
                //4. 即在f[k-2] 的前面進行查找 k -=2
                //5. 即下次迴圈 mid = f[k - 1 - 2] - 1
                k -= 2;
            } else { //找到
                //需要確定,返回的是哪個下標
                if(mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}

哈希查找

哈希查找演算法(Hashing)是一種用於高效查找數據的演算法,它將數據存儲在散列表(Hash Table)中,並利用散列函數將數據的關鍵字映射到表中的位置。哈希查找的核心思想是通過散列函數將關鍵字轉換為表中的索引,從而實現快速的查找操作。

在平均情況下,哈希查找的時間複雜度可以達到O(1)。但是,在最壞情況下,哈希查找的時間複雜度可能會退化到O(n),其中n是散列表中存儲的鍵值對數量

Java提供了用於實現哈希表(散列表)的數據結構,這就是HashMap類。HashMap是Java標準庫中最常用的哈希表實現之一,用於存儲鍵值對,並提供了快速的查找、插入和刪除操作。

通過leetcode第一題兩數之和可以瞭解哈希表的使用

代碼示例

public static int[] twoSum(int[] nums, int target) {

    int[] indexs = new int[2];

    HashMap<Integer, Integer> hashMap = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {

        if (hashMap.containsKey(nums[i])){
            indexs[0] = i;
            indexs[1] = hashMap.get(nums[i]);
            return indexs;
        }

        hashMap.put(target - nums[i],i);
    }
    return indexs;

}

二叉樹查找

二叉搜索樹是一種特殊的二叉樹,它是一種有序的樹結構,可以用於實現二叉樹查找。在二叉搜索樹中,對於每個節點,其左子樹的值都小於該節點的值,而右子樹的值都大於該節點的值。這種結構使得在二叉搜索樹中可以快速地進行查找操作。

詳細看這篇文章 二叉搜索樹


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 工作中經常會遇到監聽數組發生變化時執行相應的回調觸發邏輯,客戶應用場景中需要實現對象變數的動態監聽,當變數發生變化時觸發回調函數,實現事件發送等應用場景。 通常由以下兩種方式實現需求 一.通過改變對象原型prototype方法實現回調監聽 //創建一個數組原型對象 var arrayProtoTyp ...
  • nvm、node、vue安裝、創建vue項目 nvm作用:可以管理多個版本的node,切換node版本,下載node。 前情提要 參 考:https://zhuanlan.zhihu.com/p/519270555 下載地址:https://github.com/coreybutler/nvm-wi ...
  • 我想起了我剛工作的時候,第一次接觸RPC協議,當時就很懵,我HTTP協議用得好好的,為什麼還要用RPC協議? 於是就到網上去搜。 不少解釋顯得非常官方,我相信大家在各種平臺上也都看到過,解釋了又好像沒解釋,都在用一個我們不認識的概念去解釋另外一個我們不認識的概念,懂的人不需要看,不懂的人看了還是不懂 ...
  • 什麼是隊列? 隊列是一種線性數據結構,隊列中的元素只能先進先出; 隊列的出口端叫做隊頭,入口端叫做隊尾。 隊列的基本操作 1.入隊: 只允許在隊尾的位置放入元素,新元素的下一個位置將會成為新的隊尾; public void enQueue(int element) throws Exception{ ...
  • 匿名函數和常見是內置函數(配合匿名使用)和for迴圈的原理,異常的捕獲 匿名函數 常見的內置函數(配合匿名函數使用) 可迭代對象 迭代器對象 for迴圈內部原理 異常捕獲 匿名函數 匿名函數不需要顯示地定義函數名,使用【lambda + 參數 +表達式】的方式 lambda [arg1 [,arg2 ...
  • 文章來源:https://www.zhihu.com/question/545653479/answer/3098666967 1 內部員工吐露 每天工作其實就是負責自己片區的紅綠燈,一大早就去校對時間,然後發佈到後臺。是的,統計出來的,而且還是人工統計,有誤差請見諒 真的是很辛苦了!不過還是希望他 ...
  • 通過這個解釋,我們將瞭解當Python程式顯示類似NameError: name '' is not defined的錯誤時,即使該函數存在於腳本中,也會出現這種情況。 我們還學習了當我們使用拼寫錯誤的變數或沒有導入的內置函數時會發生什麼,以及如何在Python中避免這些錯誤。 避免在Python聲 ...
  • 本文將使用實際的例子來解釋Python的urlparse() 函數來解析和提取URL中的功能變數名稱。我們還將討論如何提高我們解析 URL 的能力和使用它們的不同組件。 用urlparse() 從 URL 中提取功能變數名稱 urlparse() 方法是Python的urllib 模塊的一部分,當你需要將URL拆分 ...
一周排行
    -Advertisement-
    Play Games
  • 通過WPF的按鈕、文本輸入框實現了一個簡單的SpinBox數字輸入用戶組件並可以通過數據綁定數值和步長。本文中介紹了通過Xaml代碼實現自定義組件的佈局,依賴屬性的定義和使用等知識點。 ...
  • 以前,我看到一個朋友在對一個系統做初始化的時候,通過一組魔幻般的按鍵,調出來一個隱藏的系統設置界面,這個界面在常規的菜單或者工具欄是看不到的,因為它是一個後臺設置的關鍵界面,不公開,同時避免常規用戶的誤操作,它是作為一個超級管理員的入口功能,這個是很不錯的思路。其實Winform做這樣的處理也是很容... ...
  • 一:背景 1. 講故事 前些天有位朋友找到我,說他的程式每次關閉時就會自動崩潰,一直找不到原因讓我幫忙看一下怎麼回事,這位朋友應該是第二次找我了,分析了下 dump 還是挺經典的,拿出來給大家分享一下吧。 二:WinDbg 分析 1. 為什麼會崩潰 找崩潰原因比較簡單,用 !analyze -v 命 ...
  • 在一些報表模塊中,需要我們根據用戶操作的名稱,來動態根據人員姓名,更新報表的簽名圖片,也就是電子手寫簽名效果,本篇隨筆介紹一下使用FastReport報表動態更新人員簽名圖片。 ...
  • 最新內容優先發佈於個人博客:小虎技術分享站,隨後逐步搬運到博客園。 創作不易,如果覺得有用請在Github上為博主點亮一顆小星星吧! 博主開始學習編程於11年前,年少時還只會使用cin 和cout ,給單片機點點燈。那時候,類似async/await 和future/promise 模型的認知還不是 ...
  • 之前在阿裡雲ECS 99元/年的活動實例上搭建了一個測試用的MINIO服務,以前都是直接當基礎設施來使用的,這次準備自己學一下S3相容API相關的對象存儲開發,因此有了這個小工具。目前僅包含上傳功能,後續計劃開發一個類似圖床的對象存儲應用。 ...
  • 目錄簡介快速入門安裝 NuGet 包實體類User資料庫類DbFactory增刪改查InsertSelectUpdateDelete總結 簡介 NPoco 是 PetaPoco 的一個分支,具有一些額外的功能,截至現在 github 星數 839。NPoco 中文資料沒多少,我是被博客園群友推薦的, ...
  • 前言 前面使用 Admin.Core 的代碼生成器生成了通用代碼生成器的基礎模塊 分組,模板,項目,項目模型,項目欄位的基礎功能,本篇繼續完善,實現最核心的模板生成功能,並提供生成預覽及代碼文件壓縮下載 準備 首先清楚幾個模塊的關係,如何使用,簡單畫一個流程圖 前面完成了基礎的模板組,模板管理,項目 ...
  • 假設需要實現一個圖標和文本結合的按鈕 ,普通做法是 直接重寫該按鈕的模板; 如果想作為通用的呢? 兩種做法: 附加屬性 自定義控制項 推薦使用附加屬性的形式 第一種:附加屬性 創建Button的附加屬性 ButtonExtensions 1 public static class ButtonExte ...
  • 在C#中,委托是一種引用類型的數據類型,允許我們封裝方法的引用。通過使用委托,我們可以將方法作為參數傳遞給其他方法,或者將多個方法組合在一起,從而實現更靈活的編程模式。委托類似於函數指針,但提供了類型安全和垃圾回收等現代語言特性。 基本概念 定義委托 定義委托需要指定它所代表的方法的原型,包括返回類 ...