(十九）查找算法-线性查找

飞熊 • 2023年5月10日下午10:44 • 后端开发 • 阅读 136

1 查找算法基本介绍

在 Java 中，常用的查找算法有4种：
（1）顺序（线性）查找
（2）二分查找/折半查找
（3）插值查找
（4）斐波那契查找

2 线性查找

2.1 最简单的线性查找

线性查找法在生活中其实是很常见的，举个栗子吧：比如，你的书架上第一层有许多书，现在你想要从里面找到《编译原理》这本书，你会怎么找呢？通常你会从第一本开始看书名，如果是的就找到了直接拿出来，如果不是就继续下一本，以此类推，其实这样一个过程就是线性查找的过程。

下面通过一个实际的案例，实现一个线性查找。
有一个数列：{1, 9, 11, -1, 34, 89, 11}，判断数列中是否包含此名称【顺序查找】。
要求：如果找到了，就提示找到，并给出下标值。
代码示例：

/**
 * 线性查找
 */
public class SeqSearch {
    public static void main(String[] args) {
        int[] arr = {1, 9, 11, -1, 34, 89, 11};

        int index = seqSearch(arr, 11);
        if (index == -1) {
            System.out.println("未找到");
        }else{
            System.out.println("元素下标：" + index);
        }

    }

    public static int seqSearch(int[] arr, int val) {
        // 线性查找是逐一比对，发现有相同的值时，就返回下标
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == val) {
                return i;
            }
        }
        return -1;
    }
}

2.2 扩展-使用泛型

上面的程序实现了一个最基础最简单的整型数组的线性查找算法，现在来进一步的思考，将这个业务场景进一步的发散，在实际的应用中，可能遇到的数据类型不是整型的，比如字符型、浮点型甚至是自定义的Object类型，如果是这样的话很显然，上面的程序就无法满足了，这时可能就会根据对应的业务场景把上面的代码再Copy一份，然后对应的修改为需要的类型，这样写没什么问题，需求当然也是能实现的，但是这个实现的方式有点…，不说了自己体会吧。

实际上我们不必如此，如果能使用一个万能的类型不就搞定了吗，在调用的时候业务方是什么类型就传什么类型，程序的可扩展性是不是极大的提高了，而且也不用再复制出来那么多重复操作的代码了，所以思维方式决定了代码行数啊！

好，下面来说解决方案，基本上在每种程序语言中都有一个专门的语言特性是用来处理这种问题的，它可以让你的类或者是方法能够处理不同的类型，这种机制就是——泛型，关于泛型的基本用法这里不做介绍，下面就来把上面的代码通过泛型进行改造。
代码示例：

public class LinearSearch {
    // 私有构造器，放置外部实例化对象
    private LinearSearch(){}

    public static <T> int search(T[] data, T target){
        for (int i = 0; i < data.length; i++) {
            if(data[i].equals(target)){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        //转换成对应的包装类
        Integer[] data = {2, 9, 5, 1, 8, 7, 3, 6};
        //target仍然可以传递数字，因为Java中有自动转换机制，编译器自动转换为对应的包装类
        int index = LinearSearch.search(data, 8);
        System.out.println(index);
    }


}