"Jianzhi offer" -- Interview Question 4: finding two-dimensional arrays

In a two-dimensional array （ Each one-dimensional array has the same length , That is, the column is fixed ）, 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 .

 

 

Increment to line , A two-dimensional array of incrementing columns Search for

*** The first method ***

One That's ok One That's ok In the process of Compare , If the following value is greater than the lookup value , Just turn To The next line Compare , And the data in the following columns do not need to be compared

#include<iostream>
#define M 4

int Search(int(*ar)[M],int col,int key)
{
	int row = M;
	for(int i = 0;i < col;i++)
	{
		for(int j = 0;j < row;j++)
		{
			if(key == ar[i][j])
			{
				return ar[i][j];
			}
			else if(key < ar[i][j])
// notes ： When the value of a column is greater than key when , There is no need to compare the following columns 
			{
				row = j;// At this time will be j Assign to row
			}
		}
	}
	return false;
}

int main()
{
	int ar[][M] = {
   {1,2,8,14},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
	int col = sizeof(ar)/sizeof(ar[0]);
	int key;
	std::cin >> key;
	if(Search(ar,col,key))
	{
		std::cout << " Yes " << key << " This number " <<std::endl;
	}
	else
	{
		std::cout << " No, " << key << " This number " <<std::endl;
	}

	return 0;
}

*** The second method ***

Based on the first method , The search in each row uses Two points search （ For an ordered sequential table, first consider using binary search , The advantage is fast , The processing effect of massive data is more obvious ）

#include<iostream>
#define M 4
int BinSearch(int *ar,int len,int key)
{
	int low = 0;
	int high = len - 1;
	int mid;
	while(low <= high)
	{
		mid = (high + low) >> 1;
		if(key == ar[mid])
		{
			return mid;
		}
		else if(key > ar[mid])
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	return mid;
}

int Search(int(*ar)[M],int col,int key)
{
	int index = col - 1;
	for(int i = 0;i < M;i++)
	{
		index = BinSearch(ar[i],index+1,key);
		if(index < 0)
		{
			return false;
		}
		if(ar[i][index] == key)
		{
			return ar[i][index];
		}
	}
	return false;
}

int main()
{
	int ar[][M] = {
   {1,2,8,14},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
	int col = sizeof(ar)/sizeof(ar[0]);
	int key;
	std::cin >> key;
	if(Search(ar,col,key))
	{
		std::cout << " Yes " << key << " This number " <<std::endl;
	}
	else
	{
		std::cout << " No, " << key << " This number " <<std::endl;
	}

	return 0;
}

 

The test case

* The two-dimensional array contains the number to look up

        Maximum   15

        minimum value   1

        A number between maximum and minimum   9

* There are no numbers to look up in a two-dimensional array  

        Greater than the maximum    20

        Less than the minimum    -3

        A number between the maximum and the minimum but without    5

* Special input test

        NULL