新手算法学习之路----二分法SmallestRectangle

            public
            class
             SmallestRectangle {

           
            public
            static
            void
             main(String[] args) {
             
            char[][]array = {{‘0‘,‘1‘,‘1‘,‘0‘},
                              {‘0‘,‘1‘,‘1‘,‘0‘},
                              {‘0‘,‘1‘,‘1‘,‘0‘},
                              {‘0‘,‘1‘,‘1‘,‘0‘}};
             int x = minArea(array,0,1);
             System.out.println(x);
            }    
 
            staticint minArea(char[][] image, int x, int y) { 
            int left,right,up,down;     //这四个变量分别表示点的左，右部分第一个含有‘1’的列的列号，以及上，下第一个含有‘1’的行的行号int low,high;               //这两个变量分别表示在while里面用来寻找中点的两端
            low = 0;
            high = y;
            int mid;
            
            //第一部分 while的功能是点的左边部分while(low<=high){                     //此while用来找点（x,y）右边的哥一个里面没有‘1’的列号boolean found = false;
                mid = low + (high- low)/2;
                for(int i =0;i<image.length;i++){  //image.length是二维数组的行号，用来对比一整列里面是否含有‘1’if(image[i][mid]==‘1‘){
                        found = true;
                        break;
                    }
                }
                if(found)
                    high = mid-1;                  
                else
                    low = mid+1;                    
            }
            left= low;   ////第二部分while功能是点的右部分。
            low = y;
            high = image[x].length-1;                // image[x].length 为二维数组列的长度。while(low<high){
                boolean found_right = false;
                mid = low+(high-low)/2;
                for(int i = 0;i<image.length;i++){
                    if(image[i][mid]==‘1‘){
                        found_right = true;
                        break;
                    }
                }
                if(found_right) low = mid+1;
                else high = mid-1;
            }
            right = low;
            
            //第三个while的作用是找到点0到x所有的含有‘1’的行的行号
            low = 0;
            high = x;
            
            while(low<=high){
                boolean found_up = false;
                mid = low+ (high-low)/2;
                for(int i =0;i<image[x].length;i++){
                    if(image[mid][i]==‘1‘){
                        found_up = true;
                        break;
                    }
                }
                if(found_up)  high = mid-1;
                else low = mid+1;                
            }
            up = low;            
            
            //第四个while的作用是找到点0到x所有的含有‘1’的行的行号
            low = x;
            high = image.length-1;            
            while(low<=high){
                boolean found_down = false;
                mid = low+ (high-low)/2;
                for(int i =0;i<image[x].length;i++){
                    if(image[mid][i]==‘1‘){
                        found_down = true;
                        break;
                    }
                }
                if(found_down)  low = mid+1;
                else high = mid-1;                
            }
            down = low;
            return (right-left)*(down-up);         
            
            
        
    }