題目描述：在一個(gè)二維數(shù)組中低斋，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)鼎姊，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)相赁。
兩種思路：
- 利用二維數(shù)組由上到下相寇，由左到右的規(guī)律，首先選取數(shù)組中右上角的數(shù)字(a[row][col])钮科，如果該數(shù)字等于要查找的數(shù)字(target)唤衫，查找過(guò)程結(jié)束；如果該數(shù)字大于要查找的數(shù)字绵脯，剔除這個(gè)數(shù)字所在的列佳励，即col--休里；如果該數(shù)字小于要查找的數(shù)字，剔除這個(gè)數(shù)字所在的行植兰，即row++。
function Find(target, array) {
var rows = 0;
var cols = array[0].length - 1;
var found = false;
if (array.length > 0) {
while (rows < array.length && cols >= 0) {
if (array[rows][cols] == target) {
found = true;
break;
} else if (array[rows][cols] > target) {
cols--;
} else {
rows++;
}
}
}
return found;
}
同樣也可以選取左下角的數(shù)字進(jìn)行比較查找璃吧。
2.把每一行看成有序遞增的數(shù)組楣导，利用二分法查找，通過(guò)遍歷每一行得到答案
function Find(target, array) {
var low = 0,
high = 0,
mid = 0;
for (var i = 0; i < array.length; i++) {
low = 0;
high = array[i].length - 1;
while (low <= high) {
mid = Math.floor((high + low) / 2);
if (target < array[i][mid]) {
high = mid - 1;
} else if (target > array[i][mid]) {
low = mid + 1;
} else {
return true;
}
}
}
return false;
}
