Search of two-dimensional array of "sword finger offer" C language version

---

Preface

Reference article ： There is a better animated version

The title is 《 The finger of the sword Offer》 Algorithm problem of the second edition .

The title is ：

In a n * m In a two-dimensional array , Each row is sorted in ascending order from left to right , Each column is sorted in ascending order from top to bottom . Please complete a function , Enter such a two-dimensional array and an integer , Determine whether the array contains the integer .

Example :

The existing matrix matrix as follows ：

[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

Limit ：

• 0 <= n <= 1000
• 0 <= m <= 1000

---

title

Observation matrix , You can find ： The lower left element Is the largest element in the column , The smallest element in the row

If The lower left element Greater than the target value , Then the target value must be above the line , The line of the element in the lower left corner can be deleted

If The lower left element Less than the target value , The target value must be to the right of the column , The column of the element in the lower left corner can be eliminated

The specific operation is to traverse from the lower left corner of the matrix , And compare with the target value ：

• row It's the number of lines column It's the number of columns
• When matrix [row] [column] > target when ： The line leads up one space （ namely row– ）, That is to say, eliminate the second part of the matrix row Row element
• When matrix [row] [column] < target when ： The line leads up one space （ namely column++ ）, That is to say, eliminate the second part of the matrix column Column elements
• When matrix [row] [column] < target when ： return true.
• If you cross the border , return false.

Picture demonstration target = 7

1、 Traverse from the element in the lower left corner of the matrix , Compare it with the target value

	1	4	6	9	15
	2	5	7	12	19
	3	8	9	16	22
	10	13	15	18	23
row	18	19	23	25	28
	column

2、 Elements 18 Greater than the target value 7, That's ok row The index moves up one space

	1	4	6	9	15
	2	5	7	12	19
	3	8	9	16	22
row	10	13	15	18	23
	18	19	23	25	28
	column

At this time, the original line does not meet the requirements , Delete the original line

	1	4	6	9	15
	2	5	7	12	19
	3	8	9	16	22
row	10	13	15	18	23
	18	19	23	25	28
	column

3、 Elements 10 Greater than the target value 7, That's ok row The index moves up one space

	1	4	6	9	15
	2	5	7	12	19
row	3	8	9	16	22
	10	13	15	18	23
	18	19	23	25	28
	column

At this time, the original line does not meet the requirements , Delete the original line

4、 Elements 3 Less than the target 7, Column column The index moves one space to the right

	1	4	6	9	15
	2	5	7	12	19
row	3	8	9	16	22
	10	13	15	18	23
	18	19	23	25	28
		column

At this time, the original column does not meet the requirements , Delete the original column

5、 Elements 8 Greater than the target value 7, That's ok row The index moves up one space

	1	4	6	9	15
row	2	5	7	12	19
	3	8	9	16	22
	10	13	15	18	23
	18	19	23	25	28
		column

At this time, the original line does not meet the requirements , Delete the original line

6、 Elements 5 Less than the target 7, Lasso moves one space to the right

	1	4	6	9	15
row	2	5	7	12	19
	3	8	9	16	22
	10	13	15	18	23
	18	19	23	25	28
			column

At this time, the original column does not meet the requirements , Delete the original column

7、 Find the target value , return true

---

Code implementation

#include <stdio.h>

#define true 1
#define false 0

int Find(int array[][5], int rows, int columns, int num)		//row Is the number of rows of the original array ,columns Is the number of columns in the original array 
{
    
	int row;		// Number of lines in the loop （ Note that there is no s）
	int column;		// Number of circular columns  （ Note that there is no s）
	row = 4;		// Start with the last line 
	column = 0;		// Start with the first in the last line （ The lower left corner ）
	if (rows == 0 || columns == 0)
	{
    
		return false;
	}
	while (column < columns && row >= 0)
	{
    
		if (array[row][column] == num)
		{
    
			return true;
		}
		else if (array[row][column] < num)
		{
    
			column++;		// To the right 
		}
		else
		{
    
			row--;			// Move up 
		}
	}
	return false;
}
void main()
{
    
	int row;		// Row number 
	int column;		// Number of columns 
	int num;		// Find the target  target
	int a[5][5] = {
    
		{
    1,4,7,11,15},
		{
    2,5,8,12,19},
		{
    3,6,9,16,22},
		{
    10,13,14,17,24},
		{
    18,21,23,26,30}
	};
	row = sizeof(a) / sizeof(a[0]);			// Find the number of rows 
	column = sizeof(a[0]) / sizeof(int);	// Find the number of columns 
	printf(" Please enter the number you want to enter :");
	scanf("%d", &num);
	printf("%d ( if 1 I found it , if 0 We didn't find out )", Find(a,row,column,num));
}