查找

一、线性表的查找

1、顺序查找 O(n)[^code]

1
2
3
4
5
6
int[] a;
int Search(int key){
	a[0]=key;//设置岗哨
	for(int i=a.length;a[i]!=key;i--){
	return i;
}

2、折半查找 O(log2(N))(下标从1开始)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int[] a;
int Search_Bin(int key){
	int low=0;
	int high=a.length
	int mid=(low+high)/2

	while(low<=high){//loe<=high
		if(key==mid)
			return mid;
		else if(key<mid){
			high=mid-1;
		}
		else
			low=mid+1;	
	}

	return 0;
}

3、分块查找

分块查找是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，
对块内节点没有排序要求，因此特别适合于节点动态变化的情况。

二、树表的查找

1、二叉排序树

1）二叉排序树的查找 O(log2(N))

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node root;
int Search(Tree T,int key){
	if(root==null || root.data==key){
		return 0;
	}

	if(key<root.data){
		Search(T.lchild,key);
		return;
	}else{
		Search(T.rchild,key);
		return;
	}
}

2）二叉排序树的插入 O(log2(N))

二叉排序树的插入 以查找为基础：查找失败则插入，查找成功则返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Node root;
int Insert(Tree T,int e){
	if(root==null){
		root=new Node();
		root.data=e;
		root.lchild=root.rchild=null;
	}

	if(e<root.data){
		Insert(T.lchild,e);
		return;
	}else{
		Insert(T.rchild,e);
		return;
	}
}

3)二叉排序树的创建 O(nlog2(N))

从空树开始，新建一个结点，查找后，再插入到合适位置

1
2
3
4
5
6
7
8
9
10
Tree T;
void CreateBST(){
	T=null;
	cin>>e;
	while(e!="*")//"*"结束符
	{
		Insert(T,e);
		cin>e;
	}
}

4)二叉排序树的删除 O(nlog2(N))

删除的过程也是查找的过程

2、平衡二叉树

三、哈希表的查找

时间复杂度为直接计算