Clear binary search Python

  • 19

    Based on my shorter Ruby version. Still using ruichang's idea to use binary search.

    def minArea(self, image, x, y):
        def first(lo, hi, check):
            while lo < hi:
                mid = (lo + hi) / 2
                if check(mid):
                    hi = mid
                    lo = mid + 1
            return lo
        top    = first(0, x,             lambda x: '1' in image[x])
        bottom = first(x, len(image),    lambda x: '1' not in image[x])
        left   = first(0, y,             lambda y: any(row[y] == '1' for row in image))
        right  = first(y, len(image[0]), lambda y: all(row[y] == '0' for row in image))
        return (bottom - top) * (right - left)

    The first function could also use the bisect module, for example:

        def first(lo, hi, check):
            self.__getitem__ = check
            return bisect.bisect(self, False, lo, hi)
        def first(lo, hi, check):
            class Checker: __getitem__ = staticmethod(check)
            return bisect.bisect(Checker(), False, lo, hi)

    The first one is a bit dirtier, and requires class Solution: instead of class Solution(object):.

  • 0

    Cool lambda!

  • 0

    Excellent solution!

  • 1

    Nice solution. bottom = first(x, len(image), lambda x: '1' not in image[x]) can be changed to bottom = first(x + 1, len(image), lambda x: '1' not in image[x])

  • 0

    I know, but that makes the code longer :-P. Especially annoying if I did it for y, then it would be too wide for Firefox which would start showing a scroll bar...

  • 0

    Among the people I know, you are the one that cares most for code length...

  • 0

    One of the most brilliant of yours so far. Kudos

  • 0
    This post is deleted!

  • 0

    @AspirinSJL: check this out. You will find it interesting. Note that Stefan's code is very clear and (very often) does not need comments (as Bob Martin once said, writing a comment is a failure for a programmer). I believe that less is more, when you know what you're doing.

  • 0

    @agave Well, like I said for my Ruby version and now also here, the basic idea was ruichang's. But yeah, I'm happy with the implementation. Though I just added some shorter but more or less dirty variations.

  • 0

    @StefanPochmann: right, I was about to ask you why you didn't use bisect.bisect_left() in some way...

  • 0

    @agave Perhaps I didn't yet know that I can "abuse" the bisect module like that. I mean, its documentation only mentions "lists" and "arrays". And I think I've only ever seen one other person do that (and it was later). So it doesn't seem mainstream.

  • 0

    @StefanPochmann: right. I didn't think it was possible, honestly... That's why I thought "I am sure he thought about using bisect but maybe it's not customizable for any check function..." But you never stop learning...

  • 0

    @StefanPochmann I have a very basic question and it would be really helpful if you can clarify. In all the solutions given why are we searching for the first column with ones on left side and first column with zeros on the right side? Similarly for top and bottom cases.

    I tried implementing this and with searching for first and last columns with ones on either side and the binary search on the right side ended in an infinite loop. It got stuck at i=2 and j=3 (for the sample input provided).

    This is the code I tried.

    It would be really helpful if you can clarify.

    Thank you!

  • 0

    @StefanPochmann I just want to consult if you have any tricks/ways to write a correct binary search (such as the one in this post)? I always struggle about the corner cases and I will always need to twist for a few times before reach to the correct solution. Thanks in advance!

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.