二维数组中的查找-白红宇

二维数组中的查找

阅读量：4154 次

发布时间：2019-05-25

本文共 2195 字，大约阅读时间需要 7 分钟。

转自：

1.1. 问题描述
在一个二维整数数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。

图1-1

1.2. 问题分析

由于数组M是一个m*n阶矩阵。矩阵M的可能情况如下：

矩阵M的特点是：

(1) 图中“

红色元素

”是以第一个元素为顶点的最大正方形对角线上的元素，这条对角线上的红色元素把矩阵的每行和每列都切割成了两部分。

(2) 行和列都是递增数列，“红色元素”所在行的左侧都比它小，右侧都比它大；所在列的上侧都比它小，下侧都比它大。

(3)矩阵M的第一个元素最小，最后一个元素最大。

算法描述：

(1)将key分别与矩阵的最大元素和最小元素比较，如果key比矩阵的最大元素大或者比最小元素小，则无须继续查找，不存在这样的key。

(2)以“红色元素”为分割点，对于行数大于等于列数的矩阵采用

列二分搜索

(如图1-2和图1-4所示矩阵)。如果key等于“红色元素”返回true；比“红色元素”大在列下侧搜索；比“红色元素”小，则key只可能在图中红色箭头围成的区域中，把这样的区域称为“

最小区域

”。发现“最小区域”后，直接进入最小区域搜索。

(3)对于行数小于列数的矩阵采用

行二分搜索

(如图1-3所示矩阵)。

行搜索算法（一行一行的二分搜索）

boolean rowSearch(int [][] matrix,int key) {	int row = matrix.length-1,col = matrix[0].length-1;	int low = 0 , high = 0,mid = 0,midVal = 0,fixMin=-1;	for (int i = 0; i <= row ; i++) {		if(fixMin != -1) {			low = 0;			high = fixMin;//如果一旦发现key
   
     matrix[i][i]) {				low = i+1;				high = col;	 			} else if(key < matrix[i][i]) {				low = 0;				high = i-1;				fixMin = high;//发现最小区域			} else {				return true;			}			}		while(low <= high) {			mid = (low + high)>>1;			midVal = matrix[i][mid];			if(key < midVal) {				high = mid -1;			} else if (key > midVal) {				low = mid + 1;			} else {				return true;//发现key			}		}							}	return false;//没有发现key}

列搜索算法（一列一列的二分搜索）

boolean colSearch(int [][] matrix,int key) {	int row = matrix.length-1,col = matrix[0].length-1;	int low = 0 , high = 0,mid = 0,midVal = 0,fixMin=-1;	for (int i = 0; i <= col ; i++) {		if(fixMin != -1) {//一旦在前一列中发现，key
   
     matrix[i][i]) {				low = i+1;				high = row;	 			} else if(key < matrix[i][i]) {				low = 0;				high = i-1;				fixMin = high;//发现最小区域			} else {				return true;			}			}		while(low <= high) {			mid = (low + high)>>1;			midVal = matrix[mid][i];			if(key < midVal) {				high = mid -1;			} else if (key > midVal) {				low = mid + 1;			} else {				return true;//发现key			}		}						}	return false;//没有发现key}

搜索主算法

boolean search(int [][] matrix,int key) {	//比最小值小	if(key
   
     matrix[row][col]) {		return false ;	}	if( row < col) {		//行数小于列数采用行搜索		return rowSearch(matrix, key);	} else {		//行数大于等于列数采用列搜索		return colSearch(matrix, key);	}}

转载地址：http://rieti.baihongyu.com/

你可能感兴趣的文章