[剣指offer]2 D配列での検索

タイトルの説明
2 D配列では、各行が左から右に増加し、各列が上から下に増加した順にソートされます.関数を完了し、このような2次元配列と整数を入力して、配列にその整数が含まれているかどうかを判断してください.
説明の入力
Array:検索する2 D配列target:検索する数値
出力の説明
戻りtrueが見つかり、戻りfalseが見つかりません
テーマ分析
題意に基づいて簡単な図を描いたので,まず2次元の配列であり,その下付きスケールの変化は2方向であり,4つの境界点に基づいて解析されるため,検索開始の位置を決定した.
A:下へ、右へ
B:左に減らし、下に増やす
C:上へ減らし、右へ増やす
D:左へ、上へ
B点またはC点から検索すると、ちょうど二叉検索ツリーが構築されることがわかります.
二叉検索ツリー(Binary Search Tree)、(また:二叉検索ツリー、二叉ソートツリー)または空のツリー、または次の性質を持つ二叉ツリー:左のサブツリーが空でない場合、左のサブツリー上のすべてのノードの値はそのルートノードの値より小さい;右のサブツリーが空でない場合、右のサブツリー上のすべてのノードの値はそのルートノードの値より大きい;その左、右のサブツリーもそれぞれ二叉ソートである木.
まず、2 D配列の行数と列数を決定し、検索値を二叉検索ツリーのルートノード(BまたはC)と比較し、等しい場合はtrueを返し、左サブツリーより小さい場合は右サブツリーを検索します.配列境界を超える場合はfalseを返します.
Cをルートノードとして検索

public class Solution {
    public boolean Find(int [][] array,int target) {

        int i = array.length -1;
        int m = array[0].length -1;
        int j = 0;

        while(i>=0 && j<=m){
            if(target == array[i][j]){
                return true;
            }else if(target >array[i][j]){
                j++;
            }else{
                i--;
            }
        }

        return false;
    }
}

Bをルートノードとして検索

public class Solution {
    public boolean Find(int [][] array,int target) {

        int i = array.length -1;
        int j = array[0].length -1;
        int n = 0;

        while(j>=0 && n<=i){
            if(target == array[n][j]){
                return true;
            }else if(target >array[n][j]){
                n++;
            }else{
                j--;
            }
        }

        return false;
    }
}