finding maximum element of a list - divide and conquer approach
Here I share my Python implementation of divide and conquer approach of finding maximum element from a list :
"""
Divide and conquer approach to find the maximum from a list
"""
def find_max(li, left, right):
if left == right:
return li[left]
mid = (left + right) / 2
max1 = find_max(li, left, mid)
max2 = find_max(li, mid+1, right)
return max1 if max1 > max2 else max2
def main():
li = [1, 5, 2, 9, 3, 7, 5, 2, 10]
print "Maximum element of the list is", find_max(li, 0, len(li)-1)
if __name__ == "__main__":
main()
Comments
I've just subscribed to this blog, so I might missing something here.
But could you please explain the reasoning for this?
Even for this example with small amount of elements, this approach will have 17 function calls, with storing all the locals and also it will have 25 comparisons. Why is it better that something simple like
max = li[0]
for el in li:
if el > max:
max = el
?
Work appreciated, but I do believe doesn't worth to be blogged.
you might consider some complex algorithms like those using dynamic programming and maybe graph algorithms to implement in python. I might suggest the "longest common sub-sequence" and "shortest path in directed graphs".
Appreciate your efforts :)
mid = (left + right) / 2
is not resulting in a integer value. Instead, you can use-
mid = int((left + right) / 2)
P.S.- I am using python 3.5
reduce(lambda x,y : x if x > y else y ,li)