《剑指offer》二维数组中的查找

问题：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：

1. 选取数组中右上角的数字
2. 如果数字等于要查找的数字，游戏结束
3. 如果数字大于要查找的数字，剔除这个数字所在的列
4. 如果数字小于要查找的数字，剔除这个数字所在的行
5. 每一步都在缩小范围，直到最终找到查找的数字，或者查找范围为空。

代码实现

#include <iostream>
#include "vector"
#include <iomanip>

using namespace std;

// 利用搜索的方法
class Solution {
    public:
        bool Find(int target, vector<vector<int> > array) {
            int rows = array.size();
            int cols = array[0].size();
            int locationX = 0;
            int locationY = cols-1;
            while (locationX < rows && locationY >=0) {
                if (array[locationX][locationY] == target) {
                    return true;
                }
                else if (array[locationX][locationY] > target) {
                    --locationY;
                }
                else {
                    ++locationX;
                }
            }
            return false;
        }
};

// 利用二分查找的方法
class DSolution {
    public:
        bool binFind(int target, vector<vector<int> > array) {
            int rows = array.size();
            int cols = array[0].size();
            for(int i=0;i<rows;i++){
                int low=0;
                int high=cols-1;
                while(low<=high){
                    int mid=(low+high)/2;
                    if(target == array[i][mid])
                        return true;
                    else if(target<array[i][mid])
                        high=mid;
                    else
                        low=mid+1;
                }
            }
            return false;
        }
};

int main(int argc, char const *argv[])
{
    int arr[4][4] = {
        1,2,8,9,
        2,4,9,12,
        4,7,10,13,
        6,8,11,15
    };
    
    vector<vector<int> > array(4);
    
    array.resize(4);
    for (int i = 0; i < 4; i++)
    {
        array[i].resize(4);
    }
    
    for (int m = 0; m < 4; m++)
    {
        for (int n = 0; n < 4; n++)
        {
            array[m][n] = arr[m][n];
        }
    }
    
    for (int m = 0; m < 4; m++)
    {
        for (int n = 0; n < 4; n++)
        {
            cout<<setw(3)<<array[m][n];
        }
        cout << "\n";
    }
    
    DSolution solution;
    int t = solution.binFind(6, array);
    cout << t;
    return 0;
}

附录

关于二分查找的实现方法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int ddbsearch(int *A, int x, int y, int v)
{
    int m;
    while (x<=y) {
        m = (x+y)/2;
        if (A[m] == v)  return 1;
        else if (A[m] > v) y = m;
        else x = m+1;
    }
    return -1;
}


int main(int argc, char const *argv[])
{
    int a[4] = {1,2,3,4};
    printf("%d\n", ddbsearch(a,0,3,4));
    return 0;
}