0%

查找-顺序查找

发表于 更新于 分类于

定义

顺序查找又称为线性查找，其算法思路是从数组中的第一个（或最后一个）记录开始，将数组中元素逐个与需要查找的关键字进行比对，若发现有相等的，则查找成功；若始终未能相等，则查找失败。

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 定义接口
interface Searcher {
	/**
	 * 从数组array中查找关键字key,如果存在则返回该关键字在数组中任意出现的位置(不局限于首次或者末次之类的),否则返回-1
	 */
	int search(int[] array, int key);
}

/**
 * 顺序表查找,时间复杂度为O(n)
 */
class LinearSearcher implements Searcher {
	@Override
	public int search(int[] array, int key) {
		int len = array.length;
		for (int i = 0; i < len; i++) {
			if (array[i] == key)
				return i;
		}
		return -1;
	}
}

LinearSearcher是标准的线性查找，这里有缺陷：在循环中每个循环实际上需要判断两次(一次是否相等,一次是否越界)，如何改进呢？其实就是设置“哨兵”：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 优化的顺序表查找,时间复杂度O(n),但是比普通顺序表查找效率高
 */
class OptimizedLinearSearcher implements Searcher {

	// 相比单纯的线性查找每次for循环需要判断两次,这里设置关键字值(即哨兵)，可以让每次for循环只判断一次
	// 当数据量比较大时,如果单纯从线性查找角度看,优化后的线性搜索优势明显
	@Override
	public int search(int[] array, int key) {
		int len = array.length;
		if (len == 0) // array为空,返回-1
			return -1;
		if (array[0] == key)
			return 0;
		array[0] = key; // array[0]不是key,那么将key赋值给array[0],将array[0]作为哨兵
		// 这里"哨兵"也可以放在数组尾部
		int i = len - 1;
		while (array[i] != key) { // 每次循环少判断一个
			i--;
		}
		if (i == 0) // 从数组尾部一直查找到array[0]才找到,说明不存在
			return -1;
		return i;
	}
}

不论是线性查找还是改进后的线性查找，其时间复杂度都为O(n)