O(log(m*n)) solution java


  • 0
    K
    public class Solution {
        int rows, cols;
        
        public boolean binarySearch(int [][] a, int left, int right, int target) {
            if(left > right) return false;
            
            int mid = (left + right) / 2;
            
            int midI = mid / cols;
            int midJ = mid % cols;
            
            if(a[midI][midJ] == target) return true;
            
            if(target < a[midI][midJ]) {
                return binarySearch(a, left, mid-1, target);
            } else {
                return binarySearch(a, mid+1, right, target);
            }
        }
        
        public boolean searchMatrix(int[][] a, int target) {
            if(a.length == 0) return false;
            
            rows = a.length;
            cols = a[0].length;
            
            return binarySearch(a, 0, cols*rows - 1 , target);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.