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

分析:

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

思路:

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

方案:

1、将二维数组转换成一维有序数组,然后通过二分法查找该有序数组找到目标数。
2、首先选取数组中右上角的数字。如果该数字等于要查找的数字,则查找过程结束;如果该数字大于要查找的数字,则剔除这个数字所在的列;如果该数字小于要查找的数字,则剔除这个数字所在的行。也就是说,如果要查找的数字不在数组的右上角,则每一次都在数组的查找范围中剔除一行或一列,这样每一步都可以缩小查找的范围,直到找到要查找的数字,或者查找范围为空。
1
2
3
4
5
6
7
8
9
10
11
12
例如:
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

代码实践:

方案一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
}
}

方案二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
示例二维数组: 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("数组中未找到该数字");
}