查找算法之线性查找法

野性酷女 2023-02-20 04:53 24阅读 0赞

> 顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术。它的查找过程为：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，如果某个记录的关键字和给定值相等，则查找成功，找到所查的记录。如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

private static int sequenceSearch(int[] arr, int key){
        
         	if (arr == null){
        
                return -1;
            }
     
            for (int i = 0; i < arr.length; i++){
        
                if (arr[i] == key){
        
                    return i;
                }
            }
    
            return -1;
        }
        public static void main(String[] args) {
        
            int[] arr = {
        10,40,70,30,80,90,20,60,50,49,48,-2};
            int index= sequenceSearch(arr, 80);
            if (index == -1){
        
                System.out.println("找不到");
            }else{
        
                System.out.println("索引" + index + "值为" + arr[index]);
            }
        }

优化：上面的程序每次循环都需要判断数组是否越界，可通过设置哨兵的方法而不必每次进行比较。在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧。【这个写法很容易错，开玩笑的写法】

private static int sequenceSearch(int[] arr, int key){
        
            if (arr == null){
        
                return -1;
            }
    
            if (arr[0] == key){
        
                return 0;
            }
    
            arr[0] = key;
            int i = arr.length - 1;
            while (arr[i] != key){
        
                i--;
            }
    
            return i == 0? -1 : i;
        }
        public static void main(String[] args) {
        
            int[] arr = {
        10,40,70,30,80,90,20,60,50,49,48,-2};
            int index= sequenceSearch(arr, -10);
            if (index == -1){
        
                System.out.println("找不到");
            }else{
        
                System.out.println("索引" + index + "值为" + arr[index]);
            }
        }

显然可知该算法的时间复杂度为O(n)【无论是否优化】。当n很大时，查找效率极为低下。用于小型数据的查找可以体现出算法简单的优点。