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
                else:
                    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
    A

    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
    A

    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. http://pastebin.com/L2WzD5Fx

    It would be really helpful if you can clarify.

    Thank you!


  • 0
    Z

    @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!


  • 0
    A

    This program is concise. However, I don't think people really write this type of code at work. However, the key of this method works is reloading the getitem method. Redefining getitem method for a class is too risky and could cause many potential problems, which is not really good practice.


  • 0

    @areshand You're only talking about my first alternative, right? Or about the other two solutions as well?


  • 0
    A

    @StefanPochmann The other two


  • 0

    @areshand Huh? The first solution doesn't do that, and the second one only does it very locally so your argument doesn't apply.


Log in to reply
 

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