【数据结构与算法】顺序查找

不念不忘少年蓝@ 2022-08-10 13:55 172阅读 0赞

*  基本思想

顺序查找是最简单的查找方法，从线性表的一端开始，依次将每个记录的关键字与给定值进行比较。

*  代码实现

/**
     * 源码名称：SeqSearch.java 
     * 日期：2014-08-13
     * 程序功能：顺序查找 
     * 版权：CopyRight@A2BGeek 
     * 作者：A2BGeek
     */
    public class SeqSearch {
    	public static int seqSearch(int[] in, int key) {
    		int length = in.length;
    		int i;
    		for (i = 0; i < length && in[i] != key; i++)
    			;
    		if (i < length) {
    			return i;
    		} else {
    			return -1;
    		}
    	}
    
    	public static int seqSearchOpt(int[] in, int key) {
    		int[] innew = extendArraySize(in, key);
    		int length = innew.length;
    		int i;
    		for (i = 0; innew[i] != key; i++)
    			;
    		if (i < length) {
    			return i;
    		} else {
    			return -1;
    		}
    	}
    
    	public static int[] extendArraySize(int[] a, int key) {
    		int[] b = new int[a.length + 1];
    		b[a.length] = key;
    		System.arraycopy(a, 0, b, 0, a.length);
    		return b;
    	}
    
    	public static void main(String[] args) {
    		int[] testCase = { 4, 5, 8, 0, 9, 1, 3, 2, 6, 7 };
    		int key = (int) (Math.random() * 10);
    		System.out.println("key is " + key);
    		long startTime = System.nanoTime();
    		// int index = seqSearch(testCase, key);
    		int index = seqSearchOpt(testCase, key);
    		long endTime = System.nanoTime();
    		System.out.println("running: " + (endTime - startTime) + "ns");
    		System.out.println("index is " + index);
    	}
    }

*  补充说明

顺序查找最关键的优化点在于循环过程，seqSearchOpt本来是出于优化的目的写的，因为每次循环的比较条件变少了，效率肯定可以提高。如果是用C语言实现，是没有问题的，但是java不支持静态数组扩展，所以效率反而没有提高。