面试问题浓缩总结
小游
2021-03-21

查找算法

# 线性表查找

# 顺序查找

顺序查找(Sequential Search) 的查找过程为：从表的一端开始， 依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。顺序查找方法既适用于线性表的顺序存储结构，又适用于线性表的链式存储结构。下面只介绍以顺序表作为存储结构时实现的顺序查找算法。

最简单的顺序查找

// 顺序表定义
type SSTable struct {
	Element []int
	Length int
}
// 最简单的顺序查找
func SearchSeq(table SSTable,key int) int {
    // 直接使用遍历来查找值
	for i:= table.Length-1;i>=0;i--{
		if table.Element[i] == key{
			return i
		}
	}
	return 0
}
func main()  {
	// 初始化顺序表
	table:=SSTable{Element: []int{0,1,2,3,4,5,6},Length: 7}
	fmt.Println(SearchSeq(table,0))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

通过设置监视来查找

func SearchSeq2(table SSTable,key int) int {
	table.Element[0] = key
	var i = 0
	for i=table.Length-1;table.Element[i]!=key;i-- {

	}
	return i
}
1
2
3
4
5
6
7
8

平均查找长度和时间复杂度

image-20210304084559494

时间复杂度为 O(n)

# 折半查找

折半查找(BinarySearch) 也称二分查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。在下面及后续的讨论中，均假设有序表是递增有序的。

折半查找的查找过程为：从表的中间记录开始，如果给定值和中间记录的关键字相等，则查找成功；**如果给定值大于或者小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，**这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。

折半查找每一次查找比较都使查找范围缩小一半，与顺序查找相比，很显然会提高查找效率。为了标记查找过程中每一次的查找区间下面分别用low和high来表示当前查找区间的下界和上界， mid为区间的中间位置。

// 折半查询
func SearchBinary(table SSTable,key int) int {
	low:=1;high:=table.Length
	for low<=high {
        // 取中间
		mid:=(low+high)/2
		if key == table.Element[mid] {
			return mid
		} else if key > table.Element[mid]{
            // 说明要查找的在mid右边，所以我们修改low指针
			low = mid+1
		} else {
			high = mid - 1
		}
	}
	return 0
}

func main()  {
	// 初始化顺序表
	table:=SSTable{Element: []int{0,5,16,20,27,30,36,44,55,60,67,71},Length: 11}
	fmt.Println(SearchBinary(table,27))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

平均查找长度和时间复杂度

image-20210304085532923

# 分块查找

这个也叫索引查找，性能介于顺序查找和折半查找之前的一种方法，分块查找的关键就是索引表必须是有序的

image-20210401143642792

image-20210401143721699

# 树表查找

# 二叉排序树

二叉排序树有下面几个定义

  1. 若它的左子树不空,则 左子树上所有点的值均小于它的根结点的值
  2. 若它的右子树不空,则 右子树上所有结点的值均大于它的根结点的值
  3. 它的左、右子树也分别为二叉排序树。

二叉排序树的重要性质 ： 中序遍历一棵二叉树同时可以得到一个节点值递增的有序序列

# 二叉排序的递归查找

// 二叉排序树的递归查找
func SearchBST(tree *BSTNode,key int) *BSTNode {
	if tree== nil || tree.Element == key{
		// 如果节点为空或者值相等，说明我们找到了
		return tree
	} else if key< tree.Element {
		// 如果key小于element，说明在左子树，左子树比 根节点小
		return SearchBST(tree.lChild,key)
	} else {
		return SearchBST(tree.rChild,key)
	}
}

func main() {
	// 构建一棵二叉排序树
	tree:=&BSTNode{Element:45}
	tree.lChild = &BSTNode{Element: 24}
	tree.lChild.lChild = &BSTNode{Element: 12}
	tree.lChild.rChild = &BSTNode{Element: 37}
	tree.rChild = &BSTNode{Element: 53}
	tree.rChild.rChild = &BSTNode{Element: 93}
	// 搜索二叉排序树
	fmt.Print(SearchBST(tree,53))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

平均查找长度： (n+1)/2

# 二叉树的插入

因为go语言限制，好像不能插值，所以只能贴一下代码了，但是大致内容还是不变的

// 二叉树的插入
func InsertBST(tree *BSTNode,element int)  {
	// 当节点为空的时候我们即可插入
	if tree == nil{
		fmt.Println("插入",tree)
		tree=&BSTNode{Element: element}
	} else if element < tree.Element{
		// 说明element应该在tree的做子树
		InsertBST(tree.lChild,element)
	} else if element > tree.Element{
		InsertBST(tree.rChild,element)
	}
}
func main() {
	// 构建一棵二叉排序树
	tree:=&BSTNode{Element:45}
	tree.lChild = &BSTNode{Element: 24}
	tree.lChild.lChild = &BSTNode{Element: 12}
	tree.lChild.rChild = &BSTNode{Element: 37}
	tree.rChild = &BSTNode{Element: 53}
	tree.rChild.rChild = &BSTNode{Element: 93}
	// 搜索二叉排序树
	fmt.Print(SearchBST(tree,53))
	// 插入二叉树
	InsertBST(tree,55)

	fmt.Println(tree)
}
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
26
27
28

# 二叉排序树的删除

// 二叉树的删除
func DeleteBST(tree *BSTNode,element int)  {
	p:=tree
	var f *BSTNode = nil
	// 首先搜索二叉树
	for p != nil {
		if p.Element == element {break}
		// f表示p的双亲节点
		f = p
		// 查找子树
		if p.Element > element{p = p.lChild} else {p = p.rChild}
	}
	// 如果没找到这个节点，我们就直接返回
	if p == nil {
		return
	}
	// 有三种情况考虑
	q:=p
	if p.lChild != nil && p.rChild != nil {
		// 如果左右节点都不为空，我们需要重新排序
		// 获取当前左节点的最右节点，找出左节点最大的值
		s:=p.lChild
		for s.rChild!=nil {
			q=s;s=s.rChild
		}
		// 我们把左节点最大的值赋值到需要删除的节点
		p.Element = s.Element
		// 这里我们判断一下当前节点和我们找到的左子树的最大节点是否相等
		if q!=p {
			// 如果不相同，就把s的左子树接到当前节点的右子树
			q.rChild = s.lChild
		} else {
			q.lChild = s.lChild
		}
		// 删除s
		s = nil
		return
	} else if q.rChild == nil{
		// 如果右子树为空，我们把左子树接上去
		p = p.lChild
	} else if p.lChild == nil{
		p = p.rChild
	}
	// 把p所值的子树挂接到其双亲节点*f的相应位置
	if f==nil {
		tree = p
	} else if q == f.lChild{
		f.lChild = p
	} else {
		f.rChild = p
	}
}


func main() {
	// 构建一棵二叉排序树
	tree:=&BSTNode{Element:45}
	tree.lChild = &BSTNode{Element: 24}
	tree.lChild.lChild = &BSTNode{Element: 12}
	tree.lChild.rChild = &BSTNode{Element: 37}
	tree.rChild = &BSTNode{Element: 53}
	tree.rChild.rChild = &BSTNode{Element: 93}
	// 搜索二叉排序树
	fmt.Print(SearchBST(tree,53))
	// 插入二叉树
	//InsertBST(tree,55)
	// 删除二叉树
	DeleteBST(tree,24)
	fmt.Println(tree)
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

image-20210304103825302

# 平衡二叉树

image-20210304104129340

# 平衡二叉树的调整方法

LL型，RR型，LR型，RL型

# B-树

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构，让我们来看看他有什么特点;

（1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；

（2）子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；

（3）关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);

（4）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

image-20210304110102900

如上图我要从上图中找到E字母，查找流程如下

（1）获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；

（2）拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；

（3）拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；

# B+树

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别

（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；

（2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；

（3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。

（4）非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;

preview

特点

1、B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；

2、B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;

3、B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。

4、B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

参考：平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了 - 知乎 (zhihu.com) (opens new window)

# 散列表查找

# 散列表构造方法

# 数字分析法

# 平方取中法

# 折叠法

# 处理冲突的方法

# 开放地址法

# 链地址法

# 散列表查找

image-20210304113456581

编辑 (opens new window)
上次更新: 2021/04/01, 17:14:55
排序算法
时间复杂度和空间复杂度

← 时间复杂度和空间复杂度→

Theme by Vdoing | Copyright © 2021-2021 小游