题目：
一个二维数组，每一行按照从左到右递增，每一列按照从上到下递增，查找数组中是否存在某个数。如数组：
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
思路：依照这样规律存放的矩阵，如果从右上角看进去，将其旋转45度，可将其视为一个二叉树；其每个父节点的左儿子都比右儿子小；因此可以考虑用二分法查找；
补充数据库知识（二叉查找树）：
二叉搜索书(BST，binary search tree)，也称二叉排序树或二叉查找树
二叉搜索树：首先看名字我们知道它肯定是一个二叉树；
再看名字，它的作用是用来搜索；
小小透露一下，它的搜索策略很像二分查找；
回忆一下二分查找，是对一个排序好的数组进行某目标数的查找，前面我又说它的搜索策略很像二分查找，那我有理由怀疑二分查找树也是排序好的，那么树是怎么排序的呢？
我来定义一个树：
对于一棵树的任意一个节点，它的左子树上所有的值，好吧，也称之为键值，都没有它的爸比大，2⃣️它的右子树的所有值比它的爸比大；而去，这个节点的左子树和右子树都是二叉搜索树；
细细一想，这竟然是个迭代思想的定义；细思极恐；
二叉查找树的查找，看起来就很重要的样子；
查找分步骤：
1 从根节点开始，如果该节点为null，则这个树为空，返回null；
2 如果树不为空，那么根节点的关键字和X进行比较。
－如果X比节点的值大，那么我们继续在右子树中查找；
－如果X比节点的值小，那么我们继续在其左子树的范围内找；
编程实现思路：可以参考使用迭代，如果X更大，则将此节点的右子节点作为下一轮迭代的输入；否则左子节点作为下一轮迭代的输入；
二叉查找树的效率取决于树的高度，最优状态是一个完全二叉树，其复杂度正比与log n。
二叉查找树的最大值在做右子节点，最小值在最左子节点；
二叉树新节点的插入和查找思路类似；
代码明天贴，今天写的貌似出一个小bug，没时间改了；
遵守承诺，贴一下代码，暂时代码是正确的哟
import java.util.Scanner; public class binarySearchTree{ public static void main(String args[]){ //让用户输入一个数字，进行判断
System.out.println(" 现在请输入一个等待查找的数字(整数):") ; Scanner sc = new Scanner(System.in) ; int target = sc.nextInt() ;
//打印出目标矩阵； int [][] data = new int [][]{{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}} ; System.out.println("目标数组是： ") ; for(int i = 0; i<data.length ; i ++ ){ for(int j = 0 ; j<data[i].length; j ++ ){ System.out.print(data[i][j] + " ") ; } System.out.print(" ") ; }
//输出判断结果 System.out.println("-----------------") ; if(find(data,target)){ System.out.println("你要查找的数字存在！ "); }else{ System.out.println("你要查找的数字不存在！ "); } } //这个函数用来判断是否存在，返回一个boolean值 public static Boolean find(int[][] data, int target){ //int temp ; int i = 0; int j = data.length - 1; while(i < data.length && j >= 0){ if(data[i][j] == target){ return true ; }else{ if(data[i][j] > target){ j = j - 1 ; }else{ i = i + 1 ; } } } return false ; } }
结果如下
现在请输入一个等待查找的数字(整数): 999 目标数组是： 1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15 ----------------- 你要查找的数字不存在！
现在请输入一个等待查找的数字(整数): 7 目标数组是： 1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15 ----------------- 你要查找的数字存在！
回去碎觉咯