做股东变更要上哪个网站/北京网站排名推广

牛客网高频算法题系列-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) {// 首先处理特殊场景，当数组为空时，不可能找到目标值，直接返回falseif (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) {// 如果当前位置的值和目标值相同，说明找到了目标值，返回truereturn true;} else if (array[x][y] > target) {// 如果当前位置的值比目标值大，则往左移动，因为左边的数更小，然后进行下一轮查找y--;} else if (array[x][y] < target) {// 如果当前位置的值比目标值小，则往下移动，因为下边的数更大，然后进行下一轮查找x++;}}// 如果查找完成没有找到目标值，则返回falsereturn 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}};// 测试用例一：期望输出：trueint target1 = 7;System.out.println(find(target1, array));// 测试用例二：期望输出：falseint target2 = 3;System.out.println(find(target2, array));}
}

$1.01^{365}\approx 37.7834343329$
$0.99^{365}\approx 0.02551796445$
相信坚持的力量！