牛客网高频算法题系列-BM18-二维数组中的查找
题目形容
在一个二维数组array中（每个一维数组的长度雷同），每一行都依照从左到右递增的程序排序，每一列都依照从上到下递增的程序排序。请实现一个函数，输出这样的一个二维数组和一个整数，判断数组中是否含有该整数。
原题目见：二维数组中的查找
解法一：二分查找法
因为原二维数组是严格有序的，即从左到右递增、从上到下递增，所以能够采纳二分查找的形式进行解决。具体处理过程如下：
- 首先解决非凡场景，当数组为空时，不可能找到目标值，间接返回false。
否则，从二维数组的右上角的地位开始，作为二分的中点，x、y别离为二维数组的坐标地位，而后循环解决直到找到目标值：
- 查找终结的条件就是x、y其中一个走到了二维数组的边界之外；
- 如果以后地位的值和目标值雷同，阐明找到了目标值，返回true；
- 如果以后地位的值比目标值大，则往左挪动，因为右边的数更小，而后进行下一轮查找；
- 如果以后地位的值比目标值小，则往下挪动，因为下边的数更大，而后进行下一轮查找。
- 最初，如果查找实现没有找到目标值，则返回false。
代码
public class Bm018 { /** * 二分查找法 * * @param target 目标值 * @param array 二维数组 * @return */ public static boolean find(int target, int[][] array) { // 首先解决非凡场景，当数组为空时，不可能找到目标值，间接返回false if (array == null || array.length == 0 || array[0].length == 0) { return false; } // 而后从二维数组的右上角的地位开始，作为二分的中点，x、y别离为二维数组的坐标地位 int x = 0, y = array[0].length - 1; // 查找终结的条件就是x、y其中一个走到了二维数组的边界之外 while (x < array.length && y >= 0) { if (array[x][y] == target) { // 如果以后地位的值和目标值雷同，阐明找到了目标值，返回true return true; } else if (array[x][y] > target) { // 如果以后地位的值比目标值大，则往左挪动，因为右边的数更小，而后进行下一轮查找 y--; } else if (array[x][y] < target) { // 如果以后地位的值比目标值小，则往下挪动，因为下边的数更大，而后进行下一轮查找 x++; } } // 如果查找实现没有找到目标值，则返回false return false; } public static void main(String[] args) { int[][] array = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}}; // 测试用例一：冀望输入：true int target1 = 7; System.out.println(find(target1, array)); // 测试用例二：冀望输入：false int target2 = 3; System.out.println(find(target2, array)); }}$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
置信保持的力量！