首页 > 代码库 > Search a 2D Matrix
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]]
这道题还是比较简单的，在一个二维数组查找一个指定元素。可以直接遍历这个数组，不过已经排好序，可以先查找在哪一行，然后在对该行进行二分查找
1 public class Solution { 2 public boolean searchMatrix(int[][] matrix, int target) { 3 boolean foundIndex = false; 4 int index = 0; 5 for(int i = 0; i < matrix.length - 1; i++){ 6 if(matrix[i][0] <= target && matrix[i + 1][0] > target){ 7 foundIndex = true; 8 index = i; 9 break;10 }11 }//for12 if(foundIndex){13 return searchByBS(matrix[index], target);14 }15 else16 return searchByBS(matrix[matrix.length - 1], target);17 }18 19 /**20 * 对数组进行二分查找21 * @param num22 * @return23 */24 public boolean searchByBS(int num[],int target){25 int low = 0;26 int high = num.length - 1;27 int middle;28 while(low <= high){29 middle = (low + high) / 2;30 if(num[middle] == target)31 return true;32 else if(num[middle] > target){33 high = middle - 1;34 }else{35 low = middle + 1;36 }//else if37 }//while38 return false;39 }40 }
Search a 2D Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。