题解 | #二维数组中的查找#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param array int整型vector<vector<>> 
     * @return bool布尔型
     */
    bool Find(int target, vector<vector<int> >& array) {
        // write code here
        // 解法二：一行一行的用二分查找;
        int row=array.size();
        int col=array[0].size();

        for(int i=0; i<row; ++i)
        {
            bool flag = false;
            int l=0, r=col-1;
            while(l<=r)
            {
                int index = (l+r)/2;
                if(array[i][index]==target)
                {
                    flag = true;
                    break;
                }
                
                if(array[i][index]<target)
                    l = index+1;
                if(array[i][index]>target)
                    r = index-1;
            }

            if(flag)
                return true;
        }

        return false;

        // 解法一：理解错了，注意arry[i+1]中的元素并不全大于arry[i]中的元素;
        // int row = array.size();
        // int col = array[0].size();

        // // 先确定行所在位置
        // int row_h=0, row_l=row-1; 
        // int row_index = 0;
        // while(row_h<=row_l)
        // {
        //     row_index = (row_h+row_l)/2;
        //     // 找到该整数
        //     if((array[row_index][0]==target) || (array[row_index][col-1]==target))
        //         return true;
        //     // 找到所在行
        //     if((array[row_index][0]<target) && (array[row_index][col-1]>target))
        //         break;
            
        //     if(array[row_index][col-1]<target)
        //         row_h = row_index+1;
        //     if(array[row_index][0]>target)
        //         row_l = row_index-1;
        // }

        // // 再确定列位置
        // int col_l=0, col_r=col-1;
        // int col_index = 0;
        // while(col_l<=col_r)
        // {
        //     col_index = (col_l+col_r)/2;
        //     // 找到该整数
        //     if(array[row_index][col_index]==target)
        //         return true;
        //     if(array[row_index][col_index]<target)
        //         col_l = col_index+1;
        //     if(array[row_index][col_index]>target)
        //         col_r = col_index-1;
        // } 
        
        // return false;
    }
};