题目：Search a 2D Matrix
数组下一行最小值比上一行最大值大，且每一行递增排列。
确定数组中是否存在给定的值。
思路：
二维空间中的折半查找。
package com.example.medium; /** * 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. * @author FuPing * */ public class SearchMatrix { /** * 二维空间的折半查找 * 改进建议:确定列的范围时，需要比较相邻的两个值，此时可以一次移动两个，来加快收敛速度 * @param matrix * @param target * @return */ public boolean searchMatrix(int[][] matrix, int target) { if(matrix == null)return false; int row = matrix.length; if(row == 0)return false; if(matrix[0] == null)return false; int column = matrix[0].length; if(column == 0)return false; if(target < matrix[0][0] && target > matrix[row - 1][column - 1])return false; int cIndex = 0; int head = 0,tail = row - 1,middle = 0; while(head <= tail){//确定行数 middle = (head + tail)/2; if(matrix[middle][0] == target){ return true; }else if(matrix[middle][0] > target){//middle行最小值大于目标值 if(middle > 0 && matrix[middle - 1][0] <= target){ middle--; break; } tail = middle - 1; }else{//middle行最小值小于目标值 if(middle < row - 1 && matrix[middle + 1][0] > target){ break; } head = middle + 1; } } if(target >= matrix[middle][0] && target <= matrix[middle][column - 1]){//目标值存在于当前行 cIndex = middle; head = 0; tail = column - 1; while(head <= tail){//行中折半查找 middle = (head + tail)/2; if(matrix[cIndex][middle] == target){ return true; }else if(matrix[cIndex][middle] > target){ tail = middle - 1; }else{ head = middle + 1; } } } return false; } public static void main(String[] args) { // TODO Auto-generated method stub long startTime = System.currentTimeMillis(); int matrix[][] = {{1, 3, 5, 7},{10, 11, 16, 20},{23, 30, 34, 50},{57, 60, 75, 80},{85, 90, 95, 98}}; System.out.println(new SearchMatrix().searchMatrix(matrix, 60)); long endTime = System.currentTimeMillis(); System.out.println("程序运行时间:"+(endTime-startTime) + "ms"); } }
题目：Search a 2D MatrixII
给定一个二维数组，数组满足下面要求：每行中的整数按从左到右的顺序进行排序；每列中的整数按照从上到下的顺序进行排序。查找数组中是否存在目标值。
For example,
Consider the following matrix:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
Given target = 5, return true.
Given target = 20, return false.
与上一题不同，下一行不一定比上一行大。
思路：
从整个二维数组的左下或右上开始查找；
假设从左下开始查找，当当前元素比目标值大，则向值减小的方向移动，即向上移动；
当当前值比目标值小，则向值增大的方向移动，即向右移动。知道不能在移动，或者找到该目标值。
bool LeetCode::searchMatrix(vector<vector<int>>& matrix, int target){ if (!matrix.size() || !matrix.at(0).size())return false; int i = 0,j = matrix.at(0).size() - 1; while (i < matrix.size() && j >= 0){ if(matrix.at(i).at(j) == target)return true;//找到目标值 else if (matrix.at(i).at(j) > target)--j;//向上移动 else ++i;//向右移动 } return false; }