一、背景

• 在上文《用二分查找算法演练一个简单的LeetCode问题》中，我们使用二分查找算法解决了一个实际问题。
• 本文将通过这个代码模板去演练一个LeetCode的复杂问题，再次加深对此算法的了解。

二、LeetCode 240. 搜索二维矩阵

• 问题链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

输入：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]], target = 5
输出：true

• 分析一下题目，很自然的会想到如下解法：

1. 将矩阵拆行N行，对每一行进行二分查找；
2. 在每行遍历过程中，可以增加一些优化措施：比如某行的首元素大于目标值，则接下来的所有元素中肯定不存在目标值；某行的尾元素小于目标值，则该行中肯定没有目标值；同理，在二分查找时如果左指针对应的值大于目标值或者右指针对应的值小于目标值，则该行中肯定没有目标值。
3. 具体演示可以参见以下动画：

三、算法

class Solution {public boolean searchMatrix(int[][] matrix, int target) {for (int i = 0; i < matrix.length; i++) {// 如果该行首的元素值等于目标值，直接返回trueif (matrix[i][0]==target){return true;}  // 如果该行首的元素值大于目标值，则该行和接下来的行的值肯定超过目标值，直接返回falseif (matrix[i][0]>target){break;}// 如果该行尾的元素值小于目标值，则该行所有的元素中肯定没有目标值，则继续在接下来的行进行查找if (matrix[i][matrix[i].length-1]<target){continue;}// 每行进行二分查找if (search(matrix[i],target)>=0){return true;}}return false;}public static int search(int[] nums, int target) {int l = 0;int r = nums.length - 1;while (l <= r) {// 如果左指针大于目标值或者右指针值小于目标值，则该数组中肯定没有目标值if (nums[r] < target || nums[l]>target) {return -1;}int mid = (l + r) / 2;if (target == nums[mid]) {return mid;} else if (target > nums[mid]) {l = mid + 1;} else {r = mid - 1;}}return -1;}}

• 提交结果：