Python Data Structure 简明教程
Python - Divide and Conquer
在分治法中，手头的问题被划分为更小的子问题，然后独立解决每个问题。当我们继续将子问题划分为更小的子问题时，最终可能会达到无法进一步划分的阶段。解决这些“原子”的最小可能子问题（部分）。所有子问题的解最终都会合并，以获得原始问题的解。
从广义上讲，我们可以通过三个步骤理解 @ {s0} 方法。
Divide/Break
此步骤涉及将问题分解为更小的子问题。子问题应表示原始问题的一部分。此步骤通常采用递归方法来划分问题，直到无法进一步划分子问题。在此阶段，子问题本质上变成了原子，但仍然表示实际问题的一部分。
Binary Search implementation
在二分搜索中，我们选取一个元素的有序列表，并开始在该列表的中间位置查找元素。如果搜索值与列表中的中间值匹配，则完成搜索。否则，我们将根据被搜索项目的值选取列表的右半部分或左半部分，从而消除列表中一半的元素。
这是可行的，因为列表是有序的，并且它比线性搜索快得多。在这里，我们根据被搜索项目的值选取列表的右半部分或左半部分，从而分离给定的列表并征服它。我们将重复这种做法，直到找到该元素，或推断出它不在列表中。
Example
def bsearch(list, val):
list_size = len(list) - 1
idx0 = 0
idxn = list_size
# Find the middle most value
while idx0 <= idxn:
midval = (idx0 + idxn)// 2
if list[midval] == val:
return midval
# Compare the value the middle most value
if val > list[midval]:
idx0 = midval + 1
else:
idxn = midval - 1
if idx0 > idxn:
return None
# Initialize the sorted list
list = [2,7,19,34,53,72]
# Print the search result
print(bsearch(list,72))
print(bsearch(list,11))