【剑指 offer】二维数组中的查找 -- c++ 实现总结

注：如果代码出现了段错误问题，可能是没有考虑到空数组（至少包括[]、[[]]两种空的二维数组），健壮性也是算法的一部分

一、暴力法

1.分析：遍历数组，如果找到就返回 true
2.代码

    // Solution 1: 运行时间：15ms 占用内存：1764k
    bool Find(int target, vector > array) {
        // for循环代码可以处理空数组，不需单独处理
        int rows = array.size();
        int columns = array[0].size();
        for (int i = 0; i < rows; ++i)
            for (int j = 0; j < columns; ++j)
            {
                if (array[i][j] == target)
                    return true;
                else
                    continue;
            }
        return false;
    }

3.复杂度
时间复杂度：O(n²)
空间复杂度：O(1)

二、N行折半查找法

1.分析：依次对每一行(列)都执行折半查找
2.代码

// Solution 2: 运行时间：15ms 占用内存：1764k
bool Find(int target, vector<vector<int> > array) {
    if (array.empty())    return false;
    if (array[0].empty()) return false; //处理空数组
    int length = array.size();

    for (int i = 0; i < length; ++i)
        // 对每一列二分查找
        for (int begin=0, end=length-1, j=length/2; begin<=end;)
        {
            if (array[i][j] == target)
                return true;
            else if (array[i][j] > target)
                end = j-1;
            else 
                begin =j+1;
            j = begin + (end-begin)/2;
        }
    return false;
}

3.复杂度
时间复杂度：O(n*lgn)
空间复杂度：O(1)

4.拓展：双折半查找

二维数组分为上下左右四个边界top，bottom，left，right：
对上边界top进行折半查找，假设终止点为E，则可以将二维数组位于终止点E右边的矩形Rr排除，因为终止点E小于其右边相邻的元素E+1，而E+1是右边矩形Rr的最小元素(左上元素)
同理，对下边界bottom折半，可以排除二维数组位于终止点E左边的矩形Rl排除，
对左边界left折半，可以排除二维数组位于终止点E下边的矩形Rb排除，
对右边界right折半，可以排除二维数组位于终止点E上边的矩形Rt排除，
一轮过去，边界范围缩小，对由新边界组成的矩形重复以上操作，直到范围缩小为只有一个元素。

三、十字分割法

我首先想到的是这种方法，不过要注意这种方法无论是从思维还是实现过程都比较麻烦，实战慎用。

1.分析：在主对角线方向上进行查找操作，直到一个元素大于目标，该终止点的左上区域与右下区域都可以排除，再递归剩下的左下、右上两个区域。
2.代码

// Solution 2: 运行时间：12ms 占用内存：1624k
bool Find_2(int target, vector<vector<int> > array) {
    if (array.empty())return false;
    if (array[0].empty())return false; //处理空数组

    //初始化栈
    typedef struct {
        int xmin=0,ymin=0,xmax,ymax;
    } stack_elem;
    stack_elem temp, newTemp;
    stack<stack_elem> s;
    temp.xmax = temp.ymax = array.size()-1;
    s.push(temp); 

    while (!s.empty()){
        newTemp = temp = s.top();
        s.pop();
        int x=temp.xmin, y=temp.ymin;


        while (true){
            // 首先确定区域是否可能包含目标值
            if (array[temp.xmin][temp.ymin]>target || array[temp.xmax][temp.ymax]<target) break; 
            if (temp.xmin>temp.xmax || temp.ymin>temp.ymax) break; 

            // 遍历过程节点分为几类
            if (array[x][y] == target) return true; // 情况1： 找到目标值
            if (array[x][y] > target){ //情况2：找到大于目标值的节点，缩小大区域为两个小区域
                newTemp.xmax = x-1;
                newTemp.ymin = y;
                if (newTemp.xmin<=newTemp.xmax && newTemp.ymin<=newTemp.ymax)
                    s.push(newTemp);
                temp.ymax = y-1;
                temp.xmin = x; 
                y = temp.ymin;
            }
            else if (x == temp.xmax){ //情况3：处理非正方形区域某一边界先溢出的情况
                temp.ymin = y+1;
                x = temp.xmin;
                ++y;
            }
            else if (y == temp.ymax){
                temp.xmin = x+1;
                y = temp.ymin;
                ++x;
            }
            else {++x,++y;} // 情况4：继续查找
        } 
    }
    return 0;
}

3.复杂度
时间复杂度：采用二分查找时为O(lgn)、采用顺序查找时为O(nlgn)
空间复杂度：O(1)

四、左下/右上元素移动法

1.分析：依次对每一行(列)都执行折半查找
2.代码

// Solution 4: 运行时间：10ms 占用内存：1504k
bool Find_3(int target, vector<vector<int> > array) {
    if (array.empty())return false;
    if (array[0].empty())return false;

    int length = array.size();
    int row=0, col=length-1;
    while (row<length && col>-1){
        if (array[row][col]==target) return true;
        if (array[row][col]>target) --col;
        else ++row;
    }
    return false;
} 

3.复杂度
时间复杂度：O(n)
空间复杂度：O(1)