Given target = 3, return 1 ( 1 corresponds to true )
Return 0 / 1 ( 0 if the element is not present, 1 if the element is present ) for this problem
思路:
把matrix看做array就行,用mid / n 得到x index,mid % n得到y index。
Solution:
Time: O(logn) Space: O(1)
public class Solution { public int searchMatrix(ArrayList<ArrayList<Integer>> a, int b) { // 0 1 2 3 // - - - - // 0 |0 1 2 3 // 1 |4 5 6 7 // 2 |8 9 10 11 int m = a.size(); int n = a.get(0).size(); int size = m * n; int left = 0; int right = size - 1; while (left <= right) { int mid = left + (right - left) / 2; int x = mid / n; int y = mid % n; if (a.get(x).get(y) == b) { return 1; } else if (a.get(x).get(y) < b) { left = mid + 1; } else { right = mid - 1; } } return 0; } }