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 +