递归二分法

递归二分法

我学到的二分法可以分为常规二分法于递归二分法,后者为帮助自己理解递归做练习。在这里我给出自己写的递归二分法,考虑的数列的升降序,函数中给了参数,默认为升序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def binary_search(list, high, item, ascend=True, low=0):
if not list:
return None
mid = (low + high) // 2
if list[mid] == item:
return mid
elif list[mid] < item:
if not ascend:
high = mid - 1
if ascend:
low = mid + 1
return binary_search(list, high, item, ascend, low)
else:
if not ascend:
low = mid + 1
if ascend:
high = mid - 1
return binary_search(list, high, item, ascend, low)


if __name__ == '__main__':
list1 = list(reversed(list(range(10))))
print(list1)
result = binary_search(list1, len(list1)-1, 4, False)
print(result)
list2 = list(range(10))
print(list2)
result = binary_search(list2, len(list2)-1, 7)
print(result)
欢迎投喂,但你的支持就是对我最佳的回馈。