8.16 - hard - 58

302. Smallest Rectangle Enclosing Black Pixels

这道题有点意思，其实每一行或者每一列都是那个rotate sorted array II的变种，就是说有重复元素。不过因为给出了其中的一个点，那么就可以拿这个点做为分界线，去找四周的框。

class Solution(object):
    def minArea(self, image, x, y):
        """
        :type image: List[List[str]]
        :type x: int
        :type y: int
        :rtype: int
        """
        top = self.search_up(image, 0, x)
        bottom = self.search_down(image, x, len(image)-1)
        left = self.search_left(image, 0, y)
        right = self.search_right(image, y, len(image[0])-1)
        #print top, bottom, left, right
        return (right - left+1) * (bottom - top+1)

    def search_up(self, image, start, end):
        while start + 1 < end:
            mid = (start + end) / 2
            if "1" in image[mid]:
                end = mid
            else:
                start = mid
        if "1" in image[start]:
            return start
        else:
            return end
    
    def search_down(self, image, start, end):
        while start + 1 < end:
            mid = (start + end) / 2
            if "1" in image[mid]:
                start = mid
            else:
                end = mid
        if "1" in image[end]:
            return end
        else:
            return start
    
    def search_left(self, image, start, end):
        while start + 1 < end:
            mid = (start + end) / 2
            if "1" in [row[mid] for row in image]:
                end = mid
            else:
                start = mid
        if "1" in [row[start] for row in image]:
            return start
        else:
            return end
    
    def search_right(self, image, start, end):
        while start + 1 < end:
            mid = (start + end) / 2
            if "1" in [row[mid] for row in image]:
                start = mid
            else:
                end = mid
        if "1" in [row[end] for row in image]:
            return end

    else:
        return start