在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
分析:
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
例如这样的一个数组,我们在查找给定的整数number是否包含在数组里之前,先在数组中确定一个数,比如右上角的9,对比9和number的关系,有三种:1. 9 = number; 2. 9 > number; 3. 9 < number。
第一种关系,9 = number,查找完成,数组中包含此整数,返回true;
第二种关系,9 > number,并且我们知道,9下面的数字要比9大,所以,最有一行排除查找范围,向左移动一列,和最上面数字8比较,如果还是比8小,那再向左移动,如果此时比8大,那么我们的查找范围应该确定在第二行第一列到第三行第一列之间,在这个缩小的范围内找到右上角,即为9,重复之前的动作直到找到相等的数值或者走到最左下角;
第三种关系,9 < number, 那么排除第一行向下走,确定第二行第四列的12是否比number大,是,向下,否,向左,以此类推。
以下是代码:
class Find {
func findTheNumInBiArray(array: [[Int]], rows: Int, collomns: Int, num: Int) -> Bool {
var found = false
if (!array.isEmpty && rows > 0 && collomns > 0) {
var row = 0
var collomn = collomns - 1
while (row < rows && collomn < collomns) {
if (array[row][collomn] == num) {
found = true
return found
} else if (array[row][collomn] > num) {
collomn -= 1
} else if (array[row][collomn] < num) {
row += 1
}
}
}
return found
}
}