现在的位置: 首页 > 综合 > 正文

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

2019年06月09日 ⁄ 综合 ⁄ 共 1074字 ⁄ 字号 评论关闭
  • 基本思想

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

  • 代码实现
/**
 * 源码名称: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不支持静态数组扩展,所以效率反而没有提高。

抱歉!评论已关闭.