# 0302. Smallest Rectangle Enclosing Black Pixels
###### tags: `Leetcode` `Binary Search` `Hard`
Link: https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/
## 思路
用binary search找四个边界
## Code

class Solution {
    public int minArea(char[][] image, int x, int y) {
        int m = image.length, n = image[0].length;
        int top = searchRows(image, 0, x, 0, n-1, true);
        int bottom = searchRows(image, x+1, m, 0, n-1, false);
        int left = searchColumns(image, 0, y, 0, m-1, true);
        int right = searchColumns(image, y+1, n, 0, m-1, false);
        return (bottom-top+1)*(right-left+1);
    }
    private int searchRows(char[][] image, int start, int end, int left, int right, boolean whiteToBlack){
        while(start<end){
            int mid = start+(end-start)/2;
            boolean find = false;
            for(int i=left; i<=right; i++){
                if(image[mid][i]=='1'){
                    find = true;
                    break;
                }
            }
            if((!find&&whiteToBlack) || (find&&!whiteToBlack)) start = mid+1;
            else end = mid;
        }
        return whiteToBlack?start:(start-1);
    }
    private int searchColumns(char[][] image, int start, int end, int top, int bottom, boolean whiteToBlack){
        while(start<end){
            int mid = start+(end-start)/2;
            boolean find = false;
            for(int i=top; i<=bottom; i++){
                if(image[i][mid]=='1'){
                    find = true;
                    break;
                }
            }
            if((!find&&whiteToBlack) || (find&&!whiteToBlack)) start = mid+1;
            else end = mid;
        }
        return whiteToBlack?start:(start-1);
    }
}