剑指offer（6）面试题4：二维数组中的查找（第二版44页）

代码：

#include<iostream>

using namespace std;

bool Find(int* test_array, int rows, int columns, int number)
{
	int min_rows = 0;//从右上角开始查找。 
	int max_columns = columns - 1;
	while(min_rows < rows && max_columns >= 0) 
	{
		if(test_array[min_rows * columns + max_columns] == number)
		{
			return true;
		}
		else if(test_array[min_rows * columns + max_columns] < number)
		{
			++min_rows;
		}
		else if(test_array[min_rows * columns + max_columns] > number)
		{
			--max_columns;
		}
	}
	
	return false;
}

int main()
{
	int test_array[4][4] = {{1, 2, 8, 9},
							{2, 4, 9, 12},
							{4, 7, 10, 13},
							{6, 8, 11, 15}};
							
	if(Find((int*)test_array, 4, 4, 7))
	{
		cout << "找到了数字7" << endl; 
	}
	else 
	{
		cout << "没有找到数字7" << endl;
	}
							
	return 0;
}
           

下面我自己的想法：

受到这两张图的启发。我发现对角线上的数是由小到大的（可以使用二分查找，大大节约了查找时间），如果我们先去比较对角线的数，将会出现下面的状态。

最后只需要查找剩下来的蓝色的部分就行啦。

写完之后发现，我的方法十分的蠢。

#include<iostream>

using namespace std;

bool Find(int* test_array, int rows, int columns, int number)
{
	int min_index = 0;//查找对角线上的元素 
	int max_index = columns - 1;
	int med_index = ((max_index - min_index)>>1) + min_index;;
	while(max_index > min_index + 1) 
	{
		med_index = ((max_index - min_index)>>1) + min_index;
		
		if(test_array[med_index * columns + med_index] == number)
		{
			return true;
		}
		else if(test_array[med_index * columns + med_index] < number)
		{
			min_index = med_index;
		}
		else if(test_array[med_index * columns + med_index] > number)
		{
			max_index = med_index;
		}
		
		
		
		if(max_index == min_index + 1)//此时，说明 min_index与 max_index相邻 
		{
			for(int i = 0; i < med_index; ++i)
			{
				for(int j = med_index; j < columns; ++j) 
				{
					if(test_array[j * columns + i] == number || test_array[i * columns + j] == number) 
					{
						return true;
					}
				}
				
			}
		}
		
	}

	
	return false;
}

int main()
{
	int test_array[4][4] = {{1, 2, 8, 9},
							{2, 4, 9, 12},
							{4, 7, 10, 13},
							{6, 8, 11, 15}};
							
	if(Find((int*)test_array, 4, 4, 7))
	{
		cout << "找到了数字7" << endl; 
	}
	else 
	{
		cout << "没有找到数字7" << endl;
	}
							
	return 0;
}