算法：判断数组中是否含有某个整数

题：在一个二维数组中，每一行都按照从左到右递增的顺序排列，每一列都按照从上到下递增的顺序排列。判断数组中是否含有某个整数。

分析：

二维数组。而且数组的排列顺序也给了规定：每一行都按照从左到右递增的顺序排列，每一列都按照从上到下递增的顺序排列。

思路:

二分查找方法，以及利用二维数组的排列顺序规则进行查找。

方案：

1、将二维数组转换成一维有序数组，然后通过二分法查找该有序数组找到目标数。

2、首先选取数组中右上角的数字。如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除这个数字所在的行。也就是说，如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

例如：
int a[5][3] = { {5,7,10}, {10,12,23}, {21,23,36}, {33,36,37}, {42,46,49} };

5,  7 , 10

10, 12, 23

21, 23, 36

33, 36, 37

42, 46, 49

代码实践：

方案一：

int arr[5][3]={ {5,7,10}, {10,12,23}, {21,23,36}, {33,36,37}, {42,46,49} };
	
int targetNumber =  33;
int numbers = sizeof(arr) / sizeof(int);

//行数 
int rowNumbers = sizeof(arr)/sizeof(arr[0]);  // 5
//列数
int lineNumbers	= sizeof(arr[0])/sizeof(int);  // 3

//转成一维数组
int arrB[numbers];
for(int i=0;i<rowNumbers;i++){
	for(int j = 0;j < lineNumbers;j++){
		arrB[i*lineNumbers+j] = arr[i][j];
	}
}
//排序
for(int i = 0; i < numbers; i++){
	for(int j = i+1; j <numbers ; j++){
		if(arrB[j] > arrB[j - 1]){			
			int temp = arrB[j];
			arrB[j] = arrB[j - 1];
			arrB[j - 1] = temp;
		}
	}
}

//二分查找
int start = 0;
int end = numbers;
int middle = (start+end)*2;

while(middle >= start || middle <= end){
	
	int num = arrB[middle];
	if (num == targetNumber) {
		printf("-----%d-----",num);
		return;
	}else if(num > targetNumber){
		middle =  (end-middle)/2 + middle;
	}else if(num < targetNumber){
		middle =  (middle-start)/2 + start;
	}
}

方案二：

/*
示例二维数组： int example[5][10]
数组的总数为： 
sizeof(example) / sizeof(int)		// sizeof(example)为该数组的大小(这里是5x10)，sizeof(int)为int类型的大小(4)
数组列数为： 
sizeof(example[0])/sizeof(int)		// sizeof(example[0])为该数组一行的大小(这里是10)
数组行数则为 ：
( sizeof(example) / sizeof(int) )/ ( sizeof(example[0]) / sizeof(int) )
*/

int arr[5][3]={ {5,7,10}, {10,12,23}, {21,23,36}, {33,36,37}, {42,46,49} };

int targetNumber =  33;
int numbers = sizeof(arr) / sizeof(int);

//行数 
int rowNumbers = sizeof(arr)/sizeof(arr[0]);  // 5
//列数
int lineNumbers	= sizeof(arr[0])/sizeof(int);  // 3

int rowIndex = 0;
bool result = false;
while(lineNumbers >= 0 && rowNumbers >= 0){
	
	int number = arr[rowIndex][lineNumbers-1];
	if (number == targetNumber) {
		result = true;
		printf("-------%d----",number);
		return;
	}else if(number > targetNumber && lineNumbers >0){
		lineNumbers--;
	}else if(number < targetNumber && rowIndex < rowNumbers){
		rowIndex++;
	}
}

if (result == false) {
	printf("数组中未找到该数字");
}