c++有序表查找的方法是什么

本篇內(nèi)容介紹了“c++有序表查找的方法是什么”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

1.折半查找法-binary search

如果線性表在排序是有序的 這種情況下我們才用順序存儲(chǔ)。

//折半查找法
int BinarySearch(int* a,int n, int key)
{
	int low=0;
	int high=n-1;
	while(low<=high)
	{
		int mid = (low+high)/2;
		if(key<a[mid])
		{
			high=mid-1;
		}
		else if(key>a[mid])
		{
			low = mid+1;
		}
		else
			return mid;
	}
	return -1;//表示失敗
}

      折半查找法類似于把靜態(tài)有序查找表分成了兩顆子樹，時(shí)間復(fù)雜度為O(log N),當(dāng)我們對(duì)順序數(shù)據(jù)已經(jīng)排序好，并且沒有頻繁插入刪除時(shí)用折半查找法。

2.插值查找法

      我們在字典中查找apple或者zoo一定不是按照折半查找法這樣 會(huì)直接從前面或者后面查找，

不一定非要mid=(low+high)/2;

mid=(low+high)/2=low+(high-low)/2;

mid = low+(high-low)((key-a[low])/(a[high]-a[low]) )

//插值查找法
int BinarySearch(int* a, int n, int key)
{
	int low=0;
	int high = n-1;
	while(low<=high)
	{
		int mid = low+(low+high)*((key-a[low])/(a[high]-a[low]));
		if(key<a[mid])
		{
			high = mid-1;
		}
		else if(key>a[mid])
		{
			low=mid+1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

此時(shí)時(shí)間復(fù)雜度還是O(longN),當(dāng)關(guān)鍵字分部比較均勻時(shí)候可用此法。

3.斐波那契查找 O(log N)

//斐波那契數(shù)列
void Fibonacci()
{
	int F[100];
	F[0]=0;
	F[1]=1;
	for(int i=2;i<=100;i++)
	{
		F[i]=F[i-1]+F[i-2];
	}
}

int Fibonacci_Search(int* a, int n, int key)
{
	int k=0;
	int low=0;
	int high=n-1;
	while(n>F[k]-1)//計(jì)算n位于斐波那契數(shù)列的位置
	{
		k++;
	}
	for(int i=n-1;i<F[k]-1;i++)
	{
		a[i]=a[n-1];
	}//將斐波那契數(shù)列 不滿地方補(bǔ)全
	while(low<=high)
	{
		mid = low+F[k-1]-1;
		if(key<a[mid])
		{
			high = mid-1;
			k=k-1;
		}
		else if(key>a[mid])
		{
			low = mid+1;
			k=k-2;
		}
		else
		{
			if(mid<=n-1)
			{
				return mid;
			}
			else
			{
				return -1;//失敗
			}
		}
	}
}

應(yīng)當(dāng)說 當(dāng)順序存儲(chǔ)無序時(shí) 采用順序查找法

當(dāng)順序存儲(chǔ)已經(jīng)排序好 我們可以采用折半查找法mid=(low+high)/2;

插值查找法mid=low+(high-low)*((key-a[low])/(a[high]-a[low]));

斐波那契法mid=low+F[k-1]=1; 
以上三中算法無非就是mid 選取的不一樣而已 不過在mid 選取時(shí)候也有加減乘除計(jì)算的。

“c++有序表查找的方法是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！