题解 | #二维数组中的查找#

using System;
using System.Collections.Generic;


class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param target int整型
     * @param array int整型二维数组
     * @return bool布尔型
     */
    public bool Find (int target, List<List<int>> array) {
        /*
        思路：一维数据的扩展，与一维数组相比，多了上下两个比较的维度。
        */
        if (array == null || array.Count == 0 || array[0].Count == 0)
            return false;
        Range range = new Range();
        range.downIndex = array.Count - 1;
        range.upIndex = 0;
        range.LeftIndex = 0;
        range.RightIndex = array[0].Count - 1;

        return this.Find(target, array, range);
    }

    private bool Find(int target, List<List<int>> array, Range range) {
        int middleIndex_H = (range.LeftIndex + range.RightIndex) / 2;
        int middleIndex_V = (range.upIndex + range.downIndex) / 2;

        int middleValue = array[middleIndex_V][middleIndex_H];
        if (middleValue == target)
            return true;

        if (middleIndex_H == range.LeftIndex && middleIndex_V == range.upIndex) {
            if(target == array[range.upIndex][range.RightIndex])
                return true;
                else if(target == array[range.downIndex][range.LeftIndex])
                return true;
                else if(target == array[range.downIndex][range.RightIndex])
                return true;
                else
                return false;
        }

        if (middleValue > target) {
            Range tempRange = new Range();
            tempRange.downIndex = middleIndex_V;
            tempRange.RightIndex = middleIndex_H;
            tempRange.LeftIndex = range.LeftIndex;
            tempRange.upIndex = range.upIndex;

            bool tempResult = this.Find(target, array, tempRange);
            if (!tempResult) {
                tempRange.LeftIndex = middleIndex_H;
                tempRange.RightIndex = range.RightIndex;
                tempResult = this.Find(target, array, tempRange);
            }

            if (!tempResult) {
                tempRange.LeftIndex = range.LeftIndex;
                tempRange.RightIndex = middleIndex_H;
                tempRange.upIndex = middleIndex_V;
                tempRange.downIndex = range.downIndex;
                tempResult = this.Find(target, array, tempRange);
            }

            return tempResult;
        } else {
            Range tempRange = new Range();
            tempRange.upIndex = middleIndex_V;
            tempRange.LeftIndex = middleIndex_H;
            tempRange.RightIndex = range.RightIndex;
            tempRange.downIndex = range.downIndex;

            bool tempResult = this.Find(target, array, tempRange);
            if (!tempResult) {
                tempRange.upIndex = range.upIndex;
                tempRange.downIndex = middleIndex_V;
                tempResult = this.Find(target, array, tempRange);
            }

            if (!tempResult) {
                tempRange.LeftIndex = range.LeftIndex;
                tempRange.RightIndex = middleIndex_H;
                tempRange.upIndex = middleIndex_V;
                tempRange.downIndex = range.downIndex;
                tempResult = this.Find(target, array, tempRange);
            }

            return tempResult;
        }
    }

    private class Range {
        public int LeftIndex {
            get;
            set;
        }
        public int RightIndex {
            get;
            set;
        }
        public int upIndex {
            get;
            set;
        }
        public int downIndex {
            get;
            set;
        }
    }
}