I'm trying to make a "shortest distance algorithm for 1D".

However, I'm confused on the recursive case. I don't know how to get the value back after the recursive calls (lines 14 and 15). How can I fix the following code?

def recCPairDist(points):
    if len(points) == 1:
        return 0
    elif len(points)== 2:
        abs(points[1]-points[0])
        #how do i assign the result final value back to "leftDist rightDist"
        #since its a recurisive, the result can be more than 1, should i store all the result in a list first?
        #then get the min(list)?

    else:
        mid = len(points) // 2
        first_half = points[:mid]
        second_half = points[mid:]
        leftDist = recCPairDist(first_half)
        rightDist = recCPairDist(second_half)
        midDist = abs(second_half[0] - first_half[1]) #i dont think this is correct since i didnt consider the recursion
        return min(leftDist,rightDist,midDist)

def cPairDist(points):
    points.sort()
    return recCPairDist(points)

P1 = [7, 4, 12, 14, 2, 10, 16, 6]

cPairDist(P1)

The expected result for P1 should be 1, since the shortest distance would be between 7 and 6.

CodePudding user response：

You're really close! There's three things you have to do:

1. For the case where there's only one point to consider, you should not return 0. For example, for the array [3, 6, 9], the answer is 3, but your given base case will return 0. This is because one of the resulting subarrays will be of length 1 for odd-length arrays, and the zero return value will propagate when you return from each recursive call.
2. You need to return the value abs(points[1]-points[0]) in the len == 2 base case explicitly using the return keyword.
3. For your recursive case, the minimum difference must be between two consecutive elements in the left half, two consecutive elements in the right half, or between the last element of the first half and the first element of the second half (two consecutive elements in the original array, but not covered in the two recursive cases). So, your midDist should compute this value.

Here is a code snippet that resolves all three of these issues:

def recCPairDist(points):
    if len(points) == 1:
        return float('inf')
    elif len(points)== 2:
        return abs(points[1]-points[0])
    else:
        mid = len(points) // 2
        first_half = points[:mid]
        second_half = points[mid:]
        leftDist = recCPairDist(first_half)
        rightDist = recCPairDist(second_half)
        midDist = abs(first_half[-1] - second_half[0])
        return min(leftDist,rightDist,midDist)