顺序查找—Java实现

说明：顺序查找适用于存储结构为顺序存储或链式存储的线性表

基本思想：顺序查找也称为线性查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值key相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于key的结点，表示查找失败

时间复杂度：

• 查找成功时的平均查找长度为（n+1）/2
• 若查找不成功，需要n+1次比较，时间复杂度为O(n)
• 所以顺序查找的时间复杂度为O(n)

实现代码如下：

//顺序查找
//时间复杂度为O(n)
//数据可以是无序的
public class OrderSearch {
    public static int search(Comparable[] a,Comparable key) {
        for (int i = 0; i < a.length; i++) {
            if (a[i]==key) {
                return i;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Integer[] a= {1,5,4,7,3,8};
        int i=search(a, 4);
        System.out.println("位置在"+(i+1));
    }
}