Leetcode 4 binary search while loop

Question

I'm trying to solve leetcode problem 4 which needs you to do binary search.

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

This is my code:

class Solution: 
def findMedianSortedArrays(self, nums1, nums2): 
    if len(nums1) > len(nums2): 
        return self.findMedianSortedArrays(nums2, nums1) 
    A, B = nums1, nums2 
    total = len(A) + len(B) 
    half = total // 2 
    l, r = 0, len(A) - 1 
    while l < r: 
        i = l + (r - l) // 2 
        j = half - i - 1 - 1 
        Aleft = A[i] if i >= 0 else float("-inf") 
        Aright = A[i + 1] if (i + 1) < len(A) else float("inf") 
        Bleft = B[j] if j >= 0 else float("-inf") 
        Bright = B[j + 1] if (j + 1) < len(B) else float("inf") 
        if Aleft <= Bright and Bleft <= Aright: 
            if total % 2: 
                return min(Aright, Bright) 
            else: 
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2 
        elif Aleft > Bright: 
            r = i - 1 
        elif Bleft > Aright: 
            l = i + 1

It gives this error note:

TypeError: None is not valid value for the expected return type double
    raise TypeError(str(ret) + " is not valid value for the expected return type double");
Line 52 in _driver (Solution.py)
    _driver()
Line 59 in <module> (Solution.py)
During handling of the above exception, another exception occurred:
TypeError: must be real number, not NoneType
Line 18 in _serialize_float (./python3/__serializer__.py)
Line 61 in _serialize (./python3/__serializer__.py)
    out = ser._serialize(ret, 'double')
Line 50 in _driver (Solution.py)

However if I change the while loop condition to just while True:

class Solution: 
def findMedianSortedArrays(self, nums1, nums2): 
    if len(nums1) > len(nums2): 
        return self.findMedianSortedArrays(nums2, nums1) 
    A, B = nums1, nums2 
    total = len(A) + len(B) 
    half = total // 2 
    l, r = 0, len(A) - 1 
    while True: 
        i = l + (r - l) // 2 
        j = half - i - 1 - 1 
        Aleft = A[i] if i >= 0 else float("-inf") 
        Aright = A[i + 1] if (i + 1) < len(A) else float("inf") 
        Bleft = B[j] if j >= 0 else float("-inf") 
        Bright = B[j + 1] if (j + 1) < len(B) else float("inf") 
        if Aleft <= Bright and Bleft <= Aright: 
            if total % 2: 
                return min(Aright, Bright) 
            else: 
                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2 
        elif Aleft > Bright: 
            r = i - 1 
        elif Bleft > Aright: 
            l = i + 1

It runs perfectly. Why the difference? How could these two different in logic? Any help will be much appreciated.

ccchoy · Accepted Answer · 2022-10-21 19:56:47Z

1

The error you see is a little obscure because LeetCode is taking your solution code and wrapping it up for execution - but 1 hint you can tell from the error is that something is returning None when it's expecting a double.

The thing that's different is that if l >= r, none of the code in the while block will execute and the function will return with an implicit None value. If you instead change to while True:, the code within will always execute at least once and if the code falls into Aleft <= Bright and Bleft <= Aright, then the function will return with a non-None value.

if you add a return <some-number-here> after the while loop at the end of the function, you won't get the same error however you won't have the right answer either since the failing test case will probably return with whatever value you hardcoded in.

In the default test case, you can see that this happens at some point in your code because l, r = 0, 0 if you add a print(l, r) at the end of the function(outside of the while loop) followed by the dummy return value.

My advice (and I know some IDEs warn about this as well) would be to use explicit returns if a function is expected to return something and try not to force consumers of your function to handle None if you can - consistent types make for happy programmers.

answered Oct 21, 2022 at 19:56

ccchoy

8328 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

ZY Cao Over a year ago

Could it be that A could have length 0, then the whole thing under while loop is not executed, thus not returning anything?

Collectives™ on Stack Overflow

Leetcode 4 binary search while loop

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related