首页 > 其他 > 详细

Search a 2D Matrix,在有序矩阵查找,二分查找的变形

时间:2016-08-18 23:06:30      阅读:243      评论:0      收藏:0      [点我收藏+]

问题描述:矩阵每一行有序,每一行的最后一个元素小于下一行的第一个元素,查找。

算法分析:这样的矩阵其实就是一个有序序列,可以使用折半查找算法。

public class SearchInSortedMatrix 
{
	public static boolean searchMatrix(int[][] matrix, int target)
	{
		int m = matrix.length;
		int n = matrix[0].length;
		int low = 0;
		int high = m*n - 1;
		while(low <= high)
		{
			int mid = (low + high)/2;
			int row = mid / n;
			int column = mid % n;
			if(matrix[row][column] == target)
			{
				return true;
			}
			else if(matrix[row][column] < target)
			{
				low = mid + 1;
			}
			else
			{
				high = mid - 1;
			}
		}
		return false;
	}
}

 

Search a 2D Matrix,在有序矩阵查找,二分查找的变形

原文:http://www.cnblogs.com/masterlibin/p/5785357.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!