《剑指Offer》二维数组中的查找
二维数组中的查找
http://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e
分享五种解题方法，仅为拓宽思路：
（注：如果代码出现了段错误问题，可能是没有考虑到空数组，健壮性也是算法的一部分）
一、左下/右上元素移动法：
十分简单巧妙，在看了徘徊的路人甲的题解才后知后觉；
设M=min(m,n)，N=max(m,n)，复杂度为O(N)，详见链接题解：
链接：https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e?f=discussion
二、双折半查找法：
是我提交时使用的方法，没有法一简洁明了，但是也挺好用，复杂度最坏情况为O(M * logN)，不过总体上还是比较优秀的，大概率可以取得O(logM + logN)的效率
二维数组分为上下左右四个边界top，bottom，left，right：
对上边界top进行折半查找，假设终止点为E，则可以将二维数组位于终止点E右边的矩形Rr排除，因为终止点E小于其右边相邻的元素E+1，而E+1是右边矩形Rr的最小元素(左上元素)
同理，对下边界bottom折半，可以排除二维数组位于终止点E左边的矩形Rl排除，
对左边界left折半，可以排除二维数组位于终止点E下边的矩形Rb排除，
对右边界right折半，可以排除二维数组位于终止点E上边的矩形Rt排除，
一轮过去，边界范围缩小，对由新边界组成的矩形重复以上操作，直到范围缩小为只有一个元素
三、N行折半法：
也是很容易就能想到的方法，每一行(列)都执行折半查找，持续M行(列)，复杂度为O(M*logN)
四（一）、简单的十字分割法：
亲测可用，使用十字将数组等分为四个区域，中间交叉点用来判断，因为左上区域和右下区域必然冲突，所以二者必然可以排除一个，即每次至少可以排除1/4的数据，接着对剩下的三个区域进行递归操作，当然可以利用左上右下元素来判断是否落在区域内来进行优化，直到只有一个元素，递归层数为：logN，不优化的话最底层节点数最多为3^logN，优化后节点数会少很多，实测效率还算不错
四（二）、另一版本的十字分割法
与上一个类似，只不过这里先在主对角线方向上进行折半查找操作，操作结束后，终止点的左上区域与右下区域都可以排除，这样就只剩下左下、右上两个区域，然后再进行递归。感觉上效率会比上个版本好，不过这个我没有去实现验证
五、暴力法
不解释，复杂度为O(M*N)
下面给出双折半查找法的代码：
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if (array.size()==0 || array[0].size()==0)
return false;
else {
int top = 0, bottom = array.size()-1;
int left = 0, right = array[0].size()-1;
int sLeft = 0, sRight = 0;
int sTop = 0, sBottom = 0;
int mid = 0;
for (;left<right || top<bottom;) {
//对上边界进行折半，可以缩小右边界
sLeft = left, sRight = right;
for (;sLeft<=sRight;) {
mid = (sLeft + sRight) / 2;
if (array[top][mid]==target) return true;
else if (array[top][mid]<target) sLeft = mid+1;
else sRight = mid-1;
}
if (mid<right) right = mid; //利用终止点缩小右边界
top++;
//对下边界进行折半，可以缩小左边界
sLeft = left, sRight = right;
for (;sLeft<=sRight;) {
mid = (sLeft + sRight) / 2;
if (array[bottom][mid]==target) return true;
else if (array[bottom][mid]<target) sLeft = mid+1;
else sRight = mid-1;
}
if (left<mid) left = mid; //利用终止点缩小左边界
bottom--;
//对左边界进行折半，可以缩小下边界
sTop = top, sBottom = bottom;
for (;sTop<=sBottom;) {
mid = (sTop + sBottom) / 2;
if (array[mid][left]==target) return true;
else if (array[mid][left]<target) sTop = mid+1;
else sBottom = mid-1;
}
if (mid<bottom) bottom = mid; //利用终止点缩小下边界
left++;
//对右边界进行折半，可以缩小上边界
sTop = top, sBottom = bottom;
for (;sTop<=sBottom;) {
mid = (sTop + sBottom) / 2;
if (array[mid][right]==target) return true;
else if (array[mid][right]<target) sTop = mid+1;
else sBottom = mid-1;
}
if (top<mid) top = mid; //利用终止点缩小上边界
right--;
}
if (array[top][left]==target) return true;
else return false;
}
}
};下面是简单的十字分割法代码：
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if (array.size()==0 || array[0].size()==0)
return false;
else {
return find_by_ten_shape_divide(array, target, 0, 0, array[0].size()-1, array.size()-1);
}
}
bool find_by_ten_shape_divide(vector<vector<int> > &datas, int target, int left, int top, int right, int bottom) {
// 递归终止的条件：当区域被分割为只有一个元素
if (left==right && top==bottom) {
if (datas[top][left] == target)
return true;
else return false;
}
// 利用头尾数据进行优化：不在区域内的直接false，可以减少递归节点数量
else if (datas[top][left]>target || datas[bottom][right]<target)
return false;
else {
// 水平、竖直方向各自等分
int cHoriz = (left + right) / 2;
int cVertic = (top + bottom) / 2;
if (datas[cVertic][cHoriz] == target)
return true;
else {
// 目标大于分割点则排除左上区域，对右下进行递归
if (datas[cVertic][cHoriz] < target) {
if (cHoriz<right && cVertic<bottom &&
find_by_ten_shape_divide(datas, target, cHoriz+1, cVertic+1, right, bottom))
return true;
}
// 否则排除右下区域，对左上进行递归
else if ((left<cHoriz || top<cVertic) &&
find_by_ten_shape_divide(datas, target, left, top, cHoriz, cVertic))
return true;
// 对右上区域进行递归
if (cHoriz < right &&
find_by_ten_shape_divide(datas, target, cHoriz+1, top, right, cVertic))
return true;
// 对左下区域进行递归
if (cVertic < bottom &&
find_by_ten_shape_divide(datas, target, left, cVertic+1, cHoriz, bottom))
return true;
return false;
}
}
}
};
