下面是使用 Java 實現的四種查找算法：
- 線性查找（Linear Search）
- 二分查找（Binary Search）
- 插值查找（Interpolation Search）
- 斐波那契查找（Fibonacci Search）
? 1. 線性查找（Linear Search）
說明：
從數組的第一個元素開始，逐個比較，直到找到目標值或遍歷完整個數組。
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 = {4, 2, 7, 1, 9, 3};int target = 7;System.out.println("Index of " + target + ": " + linearSearch(arr, target)); // 輸出 2}
}
? 2. 二分查找（Binary Search）
說明：
適用于有序數組。每次將查找區間縮小一半，效率高，時間復雜度為 O(log n)。
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 static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9, 11};int target = 7;System.out.println("Index of " + target + ": " + binarySearch(arr, target)); // 輸出 3}
}
? 3. 插值查找（Interpolation Search）
說明：
是對二分查找的優化，適用于數據分布均勻的有序數組。通過插值公式計算中間點，平均性能優于二分查找。
Java 實現：
public class InterpolationSearch {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;} else if (arr[pos] < target) {left = pos + 1;} else {right = pos - 1;}}return -1;}public static void main(String[] args) {int[] arr = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};int target = 60;System.out.println("Index of " + target + ": " + interpolationSearch(arr, target)); // 輸出 5}
}
? 4. 斐波那契查找（Fibonacci Search）
說明：
基于斐波那契數列對數組進行分割，也是一種適用于有序數組的查找算法，平均性能與二分查找相當，但減少除法運算，在某些硬件環境下效率更高。
Java 實現：
public class FibonacciSearch {public static int fibonacciSearch(int[] arr, int target) {int n = arr.length;int[] fib = new int[20];fib[0] = 0;fib[1] = 1;int i = 1;while (fib[i] < n) {fib[++i] = fib[i - 1] + fib[i - 2];}int offset = 0;while (fib[i] > 1) {int k = Math.min(offset + fib[i - 2], n - 1);if (arr[k] < target) {offset = k;fib[i] = fib[i - 1];fib[i - 1] = fib[i - 2];i--;} else if (arr[k] > target) {fib[i] = fib[i - 2];fib[i - 1] = fib[i - 1] - fib[i - 2];i--;} else {return k;}}if (fib[i - 1] == 1 && arr[offset + 1] == target) {return offset + 1;}return -1;}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};int target = 9;System.out.println("Index of " + target + ": " + fibonacciSearch(arr, target)); // 輸出 4}
}
? 查找算法對比表
| 查找算法 | 數據要求 | 時間復雜度 | 空間復雜度 | 特點 |
|---|---|---|---|---|
| 線性查找 | 無序數組 | O(n) | O(1) | 簡單，適合小數據量 |
| 二分查找 | 有序數組 | O(log n) | O(1) | 高效，常用 |
| 插值查找 | 有序數組（分布均勻） | O(log log n) ~ O(n) | O(1) | 數據均勻時性能更好 |
| 斐波那契查找 | 有序數組 | O(log n) | O(1) | 避免除法，適合特定環境 |
? 總結
- 線性查找：最簡單，但效率低，適合小數據或無序數組。
- 二分查找：最常用，適用于有序數組，效率高。
- 插值查找：適用于數據分布均勻的場景，性能優于二分查找。
- 斐波那契查找：減少除法操作，適合某些硬件環境，實現稍復雜。
在實際開發中，根據數據是否有序、數據分布、性能需求等選擇合適的查找算法。
)
