searching

---

title: 搜索 categories:

• python tags:
• python date: 2020-06-19 18:48:42

---

[toc]

搜索

1，基本搜索

1.1 要求

基本搜索是最为简单的一种搜索。即在给定的列表sourceLst中，查找目标元素target。

1.2 基本思路

通过枚举、遍历的方式，逐个比较。 一旦找到，停止向前搜索，最后返回目标值。 如果没有找到目标元素，返回-1。

1.3 参考实现

def search(sourceLst,target):
	'''
	在sourceLst中查找目标元素target,
	找到返回target在sourceLst中位置，
	没有找到就返回-1
	'''
	for inx,item in enumerate(sourceLst):
		if item==target:
			return inx
	return -1

1.4 思考与借鉴(添加哨兵)

在上面的分析与实现中，基于最坏情况下的考虑，可以看到算法的复杂度为O(n)。即与给定列表的长度线性相关。这里不防在列表的末尾追加一个目标元素target。这样就确保了待查找列表中必定存在目标元素,也就是说一定可以找到目标元素。

找到后，只需要比较该元素的位置索引是否在初始列表（追加目标元素前）的有效范围内。超出有效范围，就意味着找到的元素实际上是后来追加的元素。

代码实现

def search2(sourceLst,target):
	'''
	在sourceLst中添加目标哨兵
	确保能够找到，比较元素位置是否在有效范围内
	'''
	valid_max_inx=len(sourceLst)-1
	found_inx=0
	for inx,item in enumerate(sourceLst.append(target)):
		if item==target:
			found_inx=inx
			break
	if found_inx>valid_max_inx:
		return -1
	else:
		return found_inx

2，串搜索

待续。。。