本文共 4833 字，大约阅读时间需要 16 分钟。

顺序查找、二分查找、插值查找和斐波那契查找是数据结构中常见的查找算法，每种算法适用于不同的场景，以下是对每种算法的详细介绍和优化后的内容：

代码示例：

package com.example.datastructureandalgorithm.datastructure.search;public class SeqSearch {    public static void main(String[] args) {        int[] arr = {1, 9, 11, -1, 34, 89};        int index = seqSearch(arr, -11);        if (index == -1) {            System.out.println("没有找到");        } else {            System.out.println("找到，下标为=" + index);        }    }    public static int seqSearch(int[] arr, int value) {        for (int i = 0; i < arr.length; i++) {            if (arr[i] == value) {                return i;            }        }        return -1;    }}

2. 二分查找/折半查找二分查找用于有序数组，通过每次将查找范围缩小一半来提高效率。该算法递归地比较目标值与中间元素的值，决定下一步查找的方向。

代码示例：

package com.example.datastructureandalgorithm.datastructure.search;import java.util.ArrayList;import java.util.List;public class BinarySearch {    public static void main(String[] args) {        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};                List
    
      resIndexList = binarySearch2(arr, 0, arr.length - 1, 1);        System.out.println("resIndexList=" + resIndexList);    }    public static int binarySearch(int[] arr, int left, int right, int findVal) {        if (left > right) {            return -1;        }        int mid = (left + right) / 2;        int midVal = arr[mid];        if (findVal > midVal) {            return binarySearch(arr, mid + 1, right, findVal);        } else if (findVal < midVal) {            return binarySearch(arr, left, mid - 1, findVal);        } else {            return mid;        }    }    public static List
     
       binarySearch2(int[] arr, int left, int right, int findVal) {        if (left > right) {            return new ArrayList<>();        }        int mid = (left + right) / 2;        int midVal = arr[mid];        if (findVal > midVal) {            return binarySearch2(arr, mid + 1, right, findVal);        } else if (findVal < midVal) {            return binarySearch2(arr, left, mid - 1, findVal);        } else {            List
      
        resIndexlist = new ArrayList<>();            int temp = mid - 1;            while (temp >= 0 && arr[temp] == findVal) {                resIndexlist.add(temp);                temp--;            }            resIndexlist.add(mid);            temp = mid + 1;            while (temp < arr.length && arr[temp] == findVal) {                resIndexlist.add(temp);                temp++;            }            return resIndexlist;        }    }}
      
     
    

3. 插值查找插值查找结合了二分查找和线性插值的优点，通过计算中间点的位置来加速查找过程。这种方法适用于有序数组，且数据分布较为均匀时效率较高。

代码示例：

package com.example.datastructureandalgorithm.datastructure.search;import java.util.Arrays;public class InsertValueSearch {    public static void main(String[] args) {        int[] arr = new int[100];        for (int i = 0; i < 100; i++) {            arr[i] = i + 1;        }        int index = insertValueSearch(arr, 0, arr.length - 1, 1234);        System.out.println("index = " + index);    }    public static int insertValueSearch(int[] arr, int left, int right, int findVal) {        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {            return -1;        }        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);        int midVal = arr[mid];        if (findVal > midVal) {            return insertValueSearch(arr, mid + 1, right, findVal);        } else if (findVal < midVal) {            return insertValueSearch(arr, left, mid - 1, findVal);        } else {            return mid;        }    }}

4. 斐波那契查找（黄金分割法）斐波那契查找利用黄金分割点来减少查找范围，适用于有序数组，尤其是在数据分布较为均匀的情况下。

代码示例：

package com.example.datastructureandalgorithm.datastructure.search;public class FibonacciSearch {    public static void main(String[] args) {        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};        int index = fibonacciSearch(arr, 0, arr.length - 1, 5);        System.out.println("index = " + index);    }    public static int fibonacciSearch(int[] arr, int left, int right, int findVal) {        int n = arr.length;        if (left > right) {            return -1;        }        // 计算斐波那契数列，直到找到合适的黄金分割点        int a = 0, b = 1, c = 1;        int leftIndex = left, rightIndex = right;        while (c <= rightIndex - leftIndex) {            a = b;            b = c;            c = a + b;        }        int goldenPoint = left + (right - left) * a / b;        if (arr[goldenPoint] == findVal) {            return goldenPoint;        } else if (findVal < arr[goldenPoint]) {            return fibonacciSearch(arr, left, goldenPoint - 1, findVal);        } else {            return fibonacciSearch(arr, goldenPoint + 1, right, findVal);        }    }}

每种查找算法都有其独特的优势和适用场景，选择时需根据具体需求权衡性能和实现复杂度。