C++数据结构：线性表查找

顺序表的查找：

从数据的第一个元素或最后一个元素开始查找，直到遍历完整个数据。

存储方式为：顺序存储和链式存储都可以

假设有n个元素，最坏为n，最好为1 

平均时间复杂度：O((n+1)/2)

时间复杂度为：O(n)

 

有序表的查找：

折半查找：先确定待查找记录所在的范围，然后逐步缩小范围直到找不到或找到该记录为止。

int Search_Bin(vector<int>p, int data)
{
	int i = 0;//起始点下表
	int j = p.size()-1;//终点下标
	while (i<=j)//i的下表小于等于j的下表
	{
		int c = i + (j - i) / 2;//取中间值
		if (p[c] == data) return c;//找到的话，返回下标
		else if (p[c] > data)
		{
			j = c - 1;//缩小范围
		}
		else
		{
			i = c + 1;//缩小范围
		}
	}
	return -1;//没找到的话返回-1
}

int main()
{
    vector<int>g{ 1,2,3,4,5,6,7,8,9 };
    cout << Search_Bin(g, 6) << endl;
    return 0;
}

         

查找过程可以用二叉树表示：

 这种描述折半查找过程的二叉树，称为判定树

1 2 3 4 5 6 7 8 9

第一次折半：根节点=1+(9-1)/2=5

第二次折半：左孩子A=1+(4-1)/2=2    右孩子B=6+(9-6)/2=7

第三次折半：A的左孩子C=1+(1-1)/2=1      A的右孩子D=3+(4-3)/2=3   

                      B的左孩子E=6+(6-6)/2=6      B的右孩子F=8+(9-8)/2=8 

第四次折半：D的右孩子G=4+(4-4)/2=4      F的右孩子H=9+(9-9)/2=9                            

 树的深度代表查找最大的次数：log2（n）+1   或log2（n+1）向上取整

折半查找的平均查找长度:

 当n较大时约等于：

斐波那契查找是根据斐波那契序列的特点对表进行分割的。

F0=0，F1=1，Fi=Fi+1+Fi-2，i>=2

 斐波那契查找的平均查找的平均性能比折半好，但最坏情况下的性能比折半查找差，分割时只需要进行加减运算。

索引顺序表的查找：

 以索引顺序表示静态查找表，则使用分块查找来表现。

除了数据表之外，还需要建立一个索引表。

 上图分为三个子表，为每个子表建立一个索引项：含有关键字项，和指针项。

表中数值的特点：

• 子表中的数据均小于或等于最大关键词
• 第二个子表的树据，均大于第一个子表的树据（以此类推）
• 子表中的数据可以为无序的（没有强制要求）

分块查找的平均查找长度：

假设长度为n的表，均匀分为b块，每块含有s个记录   b= n/s   每块查找的概率为 1/b ，块中的每个记录的查找概率为 1/s。

顺序查找;

 折半查找：