Locate the row first and then find the target using binary search


  • 0

    Locate the row first and then find the target using binary search. I come out 3 ways to solve this problem using binary search but the best result is 1ms and ranked around 6.7%. If you have a better way, let me know.

    Here is my solution for your reference.

    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if(matrix.length<1 || matrix[0].length<1) return false;
            if (target<matrix[0][0] || target>matrix[matrix.length-1][matrix[0].length-1]) return false;
            
            int[] firstColumn = new int[matrix.length];
            for(int i=0;i<firstColumn.length;i++){
                firstColumn[i]=matrix[i][0];
            }
            
            int index = Arrays.binarySearch(firstColumn,target);
            if(index>=0) return true;
            else{
                
                int row=-index-1 -1; // -1 to go up to the target row
                return Arrays.binarySearch(matrix[row],target)>=0;
            }
        }
    }

Log in to reply
 

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