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

本篇內容介紹了“c++有序表查找的方法是什么”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

1.折半查找法-binary search

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

//折半查找法
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;//表示失敗
}

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

2.插值查找法

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

不一定非要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;
}

此時時間復雜度還是O(longN),當關鍵字分部比較均勻時候可用此法。

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

//斐波那契數列
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)//計算n位于斐波那契數列的位置
	{
		k++;
	}
	for(int i=n-1;i<F[k]-1;i++)
	{
		a[i]=a[n-1];
	}//將斐波那契數列 不滿地方補全
	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;//失敗
			}
		}
	}
}

應當說 當順序存儲無序時 采用順序查找法

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

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

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

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