public class Test {
    public static void main(String[] args) {
        int[][] a={
                {},{},{},{},
                {6,9}
                ,{}
        };
        System.out.println(searchArray(a,9));
    }

    /**
     * 检查这行数组中是否含有目标元素
     * @param array 待测数组
     * @param target 目标元素
     * @return 结果
     */
    public static boolean searchArray(int[][] array, int target) {
        if(array.length==0){
            return false;
        }
        int lieDown=array.length-1,lieUp=0,hang=0;//行号上下指针
        //二分法
        while(lieDown >= lieUp){
            int hanged=(lieDown+lieUp)/2;
            if(lieDown==lieUp){
                hang=lieDown;//行号已经确定
            }
            if(array[hanged].length==0){//如果发现空一维数组
                //检查最后一行(lieDown是否存在搜索目标)
                if(searchHang(array[lieDown],target)){
                    return true;
                }
                //不存在则跳过最后一行
                //因为跳过了最后一行所以hanged不会再取到刚刚这个空一维数组
                lieDown--;
                continue;
            }
            //如果幸运的在这个一维数组的第一个元素发现目标
            if(array[hanged][0]==target){
                return true;
            }else if(array[hanged][0]>target){//二分缩小范围
                lieDown=hanged-1;
            }else{//二分缩小范围
                lieUp=hanged+1;
            }
        }
        while(hang>=0){//hang不一定是目标所在的那一行
            //所以要倒着从hang开始遍历hang前面所有行
            if(searchHang(array[hang],target)){
                return true;
            }else{
                hang--;
            }
        }
        return false;
    }



    /**
     * 检查这行数组中是否含有目标元素
     * @param h 待测数组
     * @param end 目标元素
     * @return 结果
     */
    private static boolean searchHang(int[] h,int end){
        int hangLeft=0,hangRight=h.length-1;
        //二分查找原理同上
        while(hangLeft<=hangRight){
            int lied=(hangLeft+hangRight)/2;
            if(h[lied]==end){
                return true;
            }else if(h[lied]>end){
                //注意左右指针变化
                hangRight=lied-1;
            }else{
                hangLeft=lied+1;
            }
        }
        return false;
    }
}