題目描述
在一個二維數(shù)組中（每個一維數(shù)組的長度相同）张吉，每一行都按照從左到右遞增的順序排序齿梁，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)芦拿，輸入這樣的一個二維數(shù)組和一個整數(shù)士飒，判斷數(shù)組中是否含有該整數(shù)查邢。
即實現(xiàn)函數(shù)：
public boolean Find(int target, int [][] array) {}
思路
- 對每一行做二分查找
- 從左下角元素開始（因為這個位置的元素有確定的增大和減小方向，也可以是右上角）酵幕，若目標比之小則上移一步扰藕，若目標比之大則左移一步
解法1
public boolean Find(int target, int [][] array) {
for(int i=0;i<array.length;i++){
if(biDivSearch(array[i],target,0,array[i].length-1))
return true;
}
return false;
}
public boolean biDivSearch(int[] array,int target,int begin,int end){
if(begin>end)
return false;
int mid = (begin+end)/2;
if(array[mid]==target)
return true;
else if(array[mid]>target)
return biDivSearch(array,target,begin,mid-1);
else
return biDivSearch(array,target,mid+1,end);
}
解法2
public boolean Find(int target, int [][] array) {
int col = 0;
int row = array.length-1;
while(col<array[0].length && row>=0){
if(array[row][col]==target)
return true;
if(array[row][col]>target)
row --;
else if(array[row][col]<target)
col ++;
}
return false;
}
