Search 2D Array

Search a 2D Matrix Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

For example, Consider the following matrix: [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] Given target = 3, return true.

Analysis:

 every dimension is sorted, and this is for searching. so binary search is natural selection. the difference is two binary search to locate y and then x coordination. Tricky part is y should be searched first, and on row should be selected if its first value is less than target.

Review binary search:

left, right, calculated middle, compare middle element with target, adjust left and right accordingly: if target>a[mid], then left=mid+1, if target <a[mid] then right=mid-1, otherwise, found it. In this solution, for y, if searching is missed, index should be right/bottom.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

public boolean searchMatrix(int[][] matrix, int target) { int xl,xr,yu,yd,mid; //binary search y yu=0;yd=matrix.length-1; if(target<matrix[0][0])return false; while(yu<=yd){ mid=(yu+yd)/2; if(target>matrix[mid][0]){ yu=mid+1; } else if(target<matrix[mid][0]){ yd=mid-1; } else{ return true;//matrix[mid][0]; } } yu=yd; //binary search x xl=0;xr=matrix[0].length-1; while(xl<=xr){ mid=(xl+xr)/2; if(target>matrix[yu][mid]){ xl=mid+1; }else if(target<matrix[yu][mid]){ xr=mid-1; }else return true; } return false; }