{"action":"opened","issue":{"url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/108","labels_url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/108/labels{/name}","comments_url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/108/comments","events_url":"https://api.github.com/repos/cbweixin/algorithm-practice/issues/108/events","html_url":"https://github.com/cbweixin/algorithm-practice/issues/108","id":120601559,"number":108,"title":"Search a 2D Matrix II","user":{"login":"cbweixin","id":1326906,"avatar_url":"https://avatars.githubusercontent.com/u/1326906?v=3","gravatar_id":"","url":"https://api.github.com/users/cbweixin","html_url":"https://github.com/cbweixin","followers_url":"https://api.github.com/users/cbweixin/followers","following_url":"https://api.github.com/users/cbweixin/following{/other_user}","gists_url":"https://api.github.com/users/cbweixin/gists{/gist_id}","starred_url":"https://api.github.com/users/cbweixin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cbweixin/subscriptions","organizations_url":"https://api.github.com/users/cbweixin/orgs","repos_url":"https://api.github.com/users/cbweixin/repos","events_url":"https://api.github.com/users/cbweixin/events{/privacy}","received_events_url":"https://api.github.com/users/cbweixin/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2015-12-06T01:52:24Z","updated_at":"2015-12-06T01:52:24Z","closed_at":null,"body":"### Problem\r\nWrite an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:\r\n\r\n    Integers in each row are sorted in ascending from left to right.\r\n    Integers in each column are sorted in ascending from top to bottom.\r\n\r\nFor example,\r\n\r\nConsider the following matrix:\r\n\r\n    [\r\n      [1,   4,  7, 11, 15],\r\n      [2,   5,  8, 12, 19],\r\n      [3,   6,  9, 16, 22],\r\n      [10, 13, 14, 17, 24],\r\n      [18, 21, 23, 26, 30]\r\n    ]\r\n\r\n\r\nGiven target = 5, return true.\r\n\r\nGiven target = 20, return false.\r\n\r\n### Attempt 1\r\n```c++\r\nclass Solution {\r\npublic:\r\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\r\n        int m = matrix.size();\r\n        if(m==0) return false;\r\n        int n = matrix.front().size();\r\n        \r\n        int row = 0, col = 0;\r\n        // check row, if the whole row is less than target, skip\r\n        while(matrix[row][n-1] < target ) {\r\n            row++;\r\n        }\r\n        // check col, if the whole col is less than target, skip\r\n        while(matrix[m-1][col] < target){\r\n            col ++;\r\n        }\r\n        \r\n        bool res = false;\r\n        for( int i = row; i < m ; i++){\r\n            res |= binary_search(matrix[i].begin() + col, matrix[i].end(), target);\r\n        }\r\n        \r\n        return res;\r\n    }\r\n};\r\n```\r\n\r\n#### Result\r\n![image](https://cloud.githubusercontent.com/assets/1326906/11611227/ea7f45f6-9b77-11e5-821e-3df7ca3f9f61.png)\r\n\r\n#### Analysis\r\nfor test case `[[-5]]`, the `while` loop , `while(matrix[row][n-1] < target)` would throw out runtime exception.\r\nbecause row would be out of boundary after increment. \r\n\r\n### Attempt 2\r\n```c++\r\nclass Solution {\r\npublic:\r\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\r\n        int m = matrix.size();\r\n        if(m==0) return false;\r\n        int n = matrix.front().size();\r\n        \r\n        int row = 0, col = 0;\r\n        // check row, if the whole row is less than target, skip\r\n        while(row < m && matrix[row][n-1] < target) {\r\n            row++;\r\n        }\r\n        // check col, if the whole col is less than target, skip\r\n        while(col < n && matrix[m-1][col] < target ){\r\n            col ++;\r\n        }\r\n       \r\n        if(row >= m || col >= n) return false;\r\n        \r\n        bool res = false;\r\n        for( int i = row; i < m ; i++){\r\n            res |= binary_search(matrix[i].begin() + col, matrix[i].end(), target);\r\n        }\r\n        \r\n        return res;\r\n    }\r\n};\r\n```\r\n\r\n#### Result\r\n![image](https://cloud.githubusercontent.com/assets/1326906/11611248/e73f286a-9b78-11e5-9a88-76d73bfffb33.png)\r\n\r\nthe performance is not that good. need improvement. \r\n\r\n"}}