我的二进制递归函数来查找最大值

Question

我仍在学习递归原理，并试图编写一个函数，通过递归调用数组的下半部分和上半部分来返回数组中所有值的最大值。

我知道我需要找到中点，然后将列表一分为二，然后调用函数继续执行，直到每个列表的长度为1。我只是不知道如何从那里继续。

感谢您的帮助。

我的功能：

def bin_max(L):
'''
Returns max of all values in list L by recursive calls with lower and upper
halves of L. If L is empty, this returns -1e20
Ex. usage:  bin_max([ 2, 1, 6, 8, -3, 7 -5, 5])  -->  returns: 8

'''
minVal = -1e20
if L == []:
return minVal   

if len(L) == 1:
return L[0] 
mid = len(L)//2

Left  = L[:mid]
Right = L[mid:]

if len(Left)> 1:
bin_max(Left)
if len(Right)> 1:
bin_max(Right)

Answer 1

您几乎做到了，代码中有两个错误。第一个是如果条件if len(Left)> 1:和if len(Right)> 1:，则它们不是真正需要的。事实上，他们甚至可能阻止你达到基本情况。如果列表的长度小于1，则处理基本情况。

另一个是从左到右合并解决方案。从左边的子列表你们知道6是最大的数字，而在右边的子列表，你们知道8是最大的数。这些数字将通过递归调用bin_max(input_list)来重新调整。所以，您应该比较左和右的输出，以获得列表中最大的元素。

def bin_max(input_list):
"""
Returns max of all values in list L by recursive calls with lower and upper
halves of L. If L is empty, this returns -1e20
Ex. usage:  bin_max([ 2, 1, 6, 8, -3, 7 -5, 5])  -->  returns: 8
"""
# This handles if the len of list reaches less than 1
if len(input_list) == 0:
return -1e20
# If length if list is one, we return that single element
if len(input_list) == 1:
return input_list[0]
# Splitting of the list
mid = len(input_list) // 2
left = input_list[:mid]
right = input_list[mid:]
# Finding the biggest element in left sub list
left_max_value = bin_max(left)
# Finding the biggest element in right sub list
right_max_value = bin_max(right)
# Comparing the result from both sides and returning the biggest value
# You can use return max(left_max_value, right_max_value) as well if you
# don't like if-else condition
if right_max_value > left_max_value:
return right_max_value
else:
return left_max_value