数据结构之查找算法

查找算法

  在数据集合中寻找某些关键字便谓之查找。而使用不同的算法效率也不一样。因此选择合适的查找算法至关重要。

顺序查找(线性查找)

最直观，最无脑的算法。从数据集的开头开始，逐渐向后遍历，一个一个的与需要查找的关键字进行对比，若不符合则继续遍历，直到找到匹配项。若遍历完后没有相应的匹配项，则证明该数据集中没有对应的元素。

struct SSTable  //假设有数据集SSTable,类型为结构体，包含元素elem和数据集的长度TableLen
{
	int* elem;
	int TableLen;
};

int Linear_Search(SSTable ST, int key)  //ST为被查找的数据集，key为要查找的关键字
{
	for (int i = 0;i < ST.TableLen;i++)   //遍历数据集
	{
		if (ST.elem[i] == key)   //若是查找到匹配项，返回匹配项在数据集中的下标
		{
			return i;
		}
		return 0;
	} 
}

你可以想象到，假如我们这个数据集的大小是10k个元素，而匹配项在数据集的最后一位的话，那么我们需要遍历整整10k遍才能得到最终的结果！！这无疑是低效的，是一个容易理解但很笨的算法，其时间复杂度在某些情况下是极其恐怖的。因此需要更聪明的算法。

折半查找(二分查找)

一个一个的查找实在是太蠢了，我们有没有更加聪明的办法?假如这个集合是有序的(例如是递增的)，那我们可以从数组的中间值开始查起。如果当前查找的值大于匹配项，则对这个集合的右半部分(以当前中间项为分界线)进行第二次折半查找….如此反复直到找到匹配值或无法找到匹配值。

假设有一个递增的数组：[2,5,8,12,16,23,38,56,72,91]，并且想要找到数字 23。

·在第一步中我们首先找到了该数组的中间值:16，我们发现中间值比我们要查找的关键字小，因此可以判断关键字存在于数组的右半部分(如果该数组里真有关键字的匹配项的话)。

·第二步，在数组的右半部分中重复的使用折半查找:即将数组的右半部分看作一个完整的数组，找到它的中间值:56，发现起比关键值要大，因此判断匹配项可能在中间值的左边。

·第三步，对中间值的左半部分重复使用折半查找，中间值为23，找到匹配项。

因此我们可以看到，要使用这个算法，首先这个集合必须得是有序的！！有序的！！有序的！！如果拿到的是一个无序的集合则首先需要对他进行排序再使用该算法

那么如何去实现对元素集的左/右部分进行二分查找呢？我首先想到的是迭代/递归，但无论是递归还是迭代都过于复杂了。因此还存在第三种选择，使用指针来实现.
定义指针low,hight,mid，分别是指向当前要查找的部分的最低位，最高位和中间位。
当关键字比中间位要大时，则对中间值的右半部分进行查找，此时low指针应该指向mid指针所指位置的下一位，然后将mid指针所指的位置重置为low和hight指针所指的区间的中间部分。
当关键字比中间值要小时，则对中间值的左半部分进行查找，此时hight指针应该指向mid指针所知位置的上一位,然后类似的重置mid指针的位置。

int Binary_Search(SSTable ST, int key)
{
	int low = 0, hight = ST.TableLen - 1, mid;
	while (low <= hight)  //这里设置终止条件，如果hight指针出现在low指针前面，则说明该部分以及全部查找完了
	{
		mid = (hight + low) / 2;  //取中间值
		if (ST.elem[mid] == key)  
		{
			return mid;
		}
		else if (key > ST.elem[mid])  //关键字大于中间值，查找中间值的右半部分
		{
			low = mid + 1;
		}
		else  //关键字小于中间值,查找中间值的左半部分
		{
			hight = mid - 1;
		}
	}
	return 0;   //走完整个流程后仍未找到关键值，则返回0
}

树形查找

二叉排序树

  定义:任意一个节点:其左子树中每个节点的值均小于该节点，其右子树中的值均大于该节点。

   //二叉排序树的结构:
		struct BiTree
{
	int data;  //当前节点的值
    struct BiTree* lchild;  //当前节点的左孩子
	struct BiTree* rchile;  //当前节点的右孩子
};

   可以看到，从上面的排序树的任意一个非叶子节点出发，都符合左(当前选中节点的左子树中任意一个节点)<中(当前选中节点)<右的特性。

二叉排序树的查找过程

   在二叉排序树的查找都是从根节点开始。若关键字的值大于根节点则在根节点的右子树上进行查找，若是小于则在左子树上进行查找。然后依次对比每个节点的值，若大于该节点则查其右子树，若小于则反之，直至查到匹配的关键字或是至叶子节点仍不匹配。

   以上图的二叉树为例:若是要查找值为4的节点，步骤依次是:

      ●首先和根节点6进行比较，小于根节点，因此查找其左孩子

      ●和左孩子2比较，大于该节点，因此查找其右孩子

      ●找到匹配项4，查找成功。

二叉排序树的构建

void BST_insert(Bit* T, int k) //插入关键值
{
	Bit point = (Bit)malloc(sizeof(BiTree));  //创建一个节点并初始化，并初始化:将值k赋给该节点的data部分，并将其左右孩子节点指向空
	point->data = k;
	point->lchild = point->rchile = NULL;

	if (*T == NULL)  //根节点为空，则直接将刚刚创建得到节点指定为根节点
	{
		*T = point;
		return;
	}
	Bit Find_P = *T; //创建一个指向根节点的指针，用于寻找这个节点对应位置的父节点
	while (Find_P != NULL)
	{
		Find_P = (Find_P->data > k) ? Find_P->lchild : Find_P->rchile;  //若该指针所指的节点的值大于要插入的关键值,该指针指向当前节点的左孩子，否则则相反。
	}
	//当该层while循环执行完毕后，Find_P指针已经指向要插入节点的父节点
	if (Find_P->data > point->data) 
	{
		Find_P->lchild = point;
	}
	else
	{
		Find_P->rchile = point;
	}
}

void Create_BiTree(Bit* T, int arry[], int n) {  //创建排序二叉树
	T = NULL;
	int i = 0;
	while (i < n)
	{
		BST_insert(T, arry[i]);
		i++;
	}
}

效率分析

  二叉排序树的查找效率取决于树的高度。从查找过程看，二叉排序树就和二分查找相似，平均时间性能也差不多，但是二叉排序树的查找不唯一，相同的关键字可能会因为其插入的顺序不同而导致构建成的树也会不同。