天天看點

楊氏矩陣的快速查找方法(超級詳細)

介紹

楊氏矩陣是一個不論是橫向或者是縱向都是一個

數值不斷增大的元素,為了讓你們看到更清楚我

給你們特地準備了兩份例子(大家不要介意我畫的醜)

例子1:

楊氏矩陣的快速查找方法(超級詳細)

例子2:

楊氏矩陣的快速查找方法(超級詳細)

但是因為畫圖闆可以更好的解釋,咱們就用第一個舉例子。

如果是一個矩陣去查詢一個數字是否在這個矩陣裡,那麼大多數人的選擇應該是一個一個去篩查,代碼如下

楊氏矩陣的快速查找方法(超級詳細)

這個查找的方法是非常的簡單隻需要一個一個查找,如果是1000個,1000000個數字那豈不是還要循環好多好多遍,是以如果代碼這麼寫就有點挫了吧,咱們可是有遠大抱負的青年,怎麼會僅僅滿足這個代碼,接下來我将給大家講解如何更快的判斷查找的元素在不在這個矩陣裡面。

正文

前面說了

楊氏矩陣是一個橫縱都是在遞增的矩陣,這樣咱們就可以找到一個規律,接下來由我給大家畫出來:

楊氏矩陣的快速查找方法(超級詳細)

大家可以看到我給這個矩陣畫了兩個框框

什麼意思呢???

大家請看這個藍色框框裡面的值,都是不斷地變大的

再看看這個紫色的(不太清楚)也是不斷地遞增

這個呢就是楊氏矩陣的規律,那麼有的人可能就會問

啊?這個不就是遞增嘛,這個規律跟加快數字的查找有什麼關系啊???

接下來我再畫個圖給大家介紹一下這兩個框框的意思

楊氏矩陣的快速查找方法(超級詳細)

大家可以看到這個5是這個行最大的一個數,是以說

如果我們要查找的數比5大,那就說明在第1行找不到和我要查找的值一樣的數了(因為已經比這一行所有的數都要大了)是以呢我們就可以換到第2行再去判斷

楊氏矩陣的快速查找方法(超級詳細)

如此往複如果我們要查找的值比這一行最後一個元素還要大那麼我們就可以換到下一行,這裡關于行的判定解釋完了,接下來到了列的判斷:

楊氏矩陣的快速查找方法(超級詳細)

大家可以看到這個深紫色的圓環依舊是圈在了最右上角的元素上面,大家是不是還可以發現:

楊氏矩陣的快速查找方法(超級詳細)

大家可以看到這個右上角的5是綠色圈圈裡面最小的一個數,是以大家也應該猜到了,當要查找的元素比5小時,那麼就可以去第三列查找了,因為第四最小的數都比我要查找的數大是以我們就可以(4-1=3)去查找第三列

如果我們設定的是N這麼大的矩陣那麼他的長寬都是N:

楊氏矩陣的快速查找方法(超級詳細)

這樣以來右上角的元素就為(0,N-1)了,因為長度是5,是以從0開始我的最大值就是(N-1),如此往複

如果我們要查找3,那麼我們就可以先進行判斷

楊氏矩陣的快速查找方法(超級詳細)

咱們用黑色将3圈了出來,由于3比5小,也就是3比右上角的數要小是以我們就(Y-1)這下我們的Y就指向了綠字3所對應的列;

楊氏矩陣的快速查找方法(超級詳細)

就這樣第4列被咱們删除掉,現在右上角的數為4,但是4依舊比3大于是我們繼續(Y-1),這樣我們的縱坐标就指向了3;

楊氏矩陣的快速查找方法(超級詳細)

查找到了3,當然查找别的值也是如此往複是不是比之前的一個一個查找塊很多一次性就可以排除一行或者列,

當然左下角也是可以的,但是左上角和右下角就不建議;好的接下來代碼實作,為了更直覺的觀看我将用函數來進行處理(初始化函數):

int main()
{
	printf("請輸入矩陣的大小\n");
	int n = 0;
	scanf("%d", &n);
	//好的接下來我們将對矩陣初始化
	int arr[50][50] = { 0 };
	int i, j;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			arr[i][j] = i + j + 1;
			printf("%d ", arr[i][j]);
		}
		printf("\n");
	}
	return 0;
}
           
5e f5 d3