首页 > 代码库 > 【LeetCode题目记录-13】二分搜索排序后的二维数组
【LeetCode题目记录-13】二分搜索排序后的二维数组
Search a 2D Matrix
Writean 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
.
【分析-原创】
/** * 创建时间:2014年9月24日 上午11:26:06 项目名称:Test * * @author Cao Yanfeng * @since JDK 1.6.0_21 类说明: 查找排序后的二维矩阵是否存在一个数 应用两层的二分查找,第一层是查找行 */ public class FindMatrixTest { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[][] matrix = { { 1, 3, 5, 7 }, { 10, 11, 16, 20 }, { 23, 30, 34, 50 } }; System.out.println(searchMatrix(matrix, 13)); } public static boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; int n = matrix[0].length; int i = 0, j = m - 1; while (i <= j) { int middleRow = i + ((j - i) >> 1); if (target < matrix[middleRow][0]) { j = middleRow - 1; continue; } else if (target > matrix[middleRow][n - 1]) { i = middleRow + 1; continue; } else if (target >= matrix[middleRow][0] && target <= matrix[middleRow][n - 1]) { return find(matrix[middleRow], 0, n - 1, target); } } return false; } public static boolean find(int[] matrixRow, int start, int end, int target) { while (start <= end) { int middle = start + ((end - start) >> 1); if (matrixRow[middle] == target) { return true; } else if (matrixRow[middle] > target) { end = middle - 1; } else if (matrixRow[middle] < target) { start = middle + 1; } } return false; } }
【LeetCode题目记录-13】二分搜索排序后的二维数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。