劍指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;
}