Easy AC Java solutions, Binary Search


  • 0

    Two while loops, searching row first then search the column. Both using binary search

    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            
            if(matrix == null || matrix.length == 0)
            {
                return false;
            }
            int rowLength = matrix.length - 1, colunmLength = matrix[0].length - 1;
            int rowLow = 0, rowHigh = rowLength;
            int columnLow = 0, columnHigh = colunmLength;
            int row = 0, column = 0;
            while(rowLow <= rowHigh)
            {
                int middle = (rowLow + rowHigh) / 2;
                if (middle == rowLength ||( matrix[middle][0] <= target && matrix[middle + 1][0] > target))
                {
                    row = middle;
                    break;
                }
                else if (matrix[middle][0] > target)
                {
                    rowHigh = middle - 1;;
                }
                else
                {
                    rowLow = middle + 1;
                }
            }
            while(columnLow <= columnHigh)
            {
                int middle = (columnLow + columnHigh) / 2;
                if (middle > colunmLength || middle < 0 || matrix[row][0] > target || matrix[row][colunmLength] < target)
                {
                    return false;
                }
                if (matrix[row][middle] == target)
                {
                    return true;
                }
                else if(matrix[row][middle] < target)
                {
                    columnLow = middle + 1;
                }
                else
                {
                    columnHigh = middle - 1;
                }
            }
            return false;
        }
    }```

Log in to reply
 

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