1 parent 63d8cad commit 83c104eCopy full SHA for 83c104e
2 files changed
maths/find_max_recursion.py
@@ -0,0 +1,25 @@
1
+# Divide and Conquer algorithm
2
+def find_max(nums, left, right):
3
+ """
4
+ find max value in list
5
+ :param nums: contains elements
6
+ :param left: index of first element
7
+ :param right: index of last element
8
+ :return: max in nums
9
+
10
+ >>> nums = [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
11
+ >>> find_max(nums, 0, len(nums) - 1) == max(nums)
12
+ True
13
14
+ if left == right:
15
+ return nums[left]
16
+ mid = (left + right) >> 1 # the middle
17
+ left_max = find_max(nums, left, mid) # find max in range[left, mid]
18
+ right_max = find_max(nums, mid + 1, right) # find max in range[mid + 1, right]
19
20
+ return left_max if left_max >= right_max else right_max
21
22
23
+if __name__ == "__main__":
24
+ nums = [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
25
+ assert find_max(nums, 0, len(nums) - 1) == 10
maths/find_min_recursion.py
+def find_min(nums, left, right):
+ find min value in list
+ :return: min in nums
+ >>> find_min(nums, 0, len(nums) - 1) == min(nums)
+ left_min = find_min(nums, left, mid) # find min in range[left, mid]
+ right_min = find_min(nums, mid + 1, right) # find min in range[mid + 1, right]
+ return left_min if left_min <= right_min else right_min
+ assert find_min(nums, 0, len(nums) - 1) == 1
0 commit comments