分而治之

还有一种分治法，将问题简化为一个子问题。<一个href="//www.parkandroid.com/wiki/binary-search/" class="wiki_link" title="二分查找" target="_blank">二分查找是一个流行的例子，使用减少和征服。二分查找查找已排序的列表，以查看列表中是否存在所需元素。它通过在程序的每次迭代期间减半搜索空间有效地做到了这一点。基本上，二分查找查找列表的中间，问“我要查找的元素比这个大还是小?”然后将列表切成两半，只在元素较小的情况下搜索左侧列表，在元素较大的情况下搜索右侧列表。它重复这个过程，直到找到它要查找的元素(或者报告该元素根本不在列表中)。

描述你将如何使用递减和征服方法在一本350页的教科书中找到第88页。

把书翻到任意一页。如果你翻开的页码大于88，把一些页码翻到书的开头(如果页码小于88，把一些页码翻到书的结尾)。现在看看你翻到的新页码。如果数量少于88,翻转一定这本书的末尾(你把数量应该减少每次迭代,因为你不想失去进步的过度),如果数量大于88,把一些对这本书的开始的页面数。重复，直到你找到88页。

如何使用分治法:

• 给定一个问题，找出若干小得多的子问题。
• 递归地解决每个子问题(这样做直到子问题是一个基本情况)。
• 将这些解决方案组合成一个解决主要问题的方案。

计算机科学:
分治算法通常遵循一种通用模式:它们解决规模问题 $n$通过递归地解决 $一个$子问题的大小 $\ dfrac {n} {b} ，然后把这些答案结合起来 O （ n d ） O (n ^ d) 时间。这种一般形式可以用下列递归关系表示: T （ n ） ＝ 一个 T （ n b ） + O （ n d ） ． T(n) = aT(\dfrac{n}{b}) + O(n^d)。 T（n）＝一个T（bn）+O（nd）．的<一个目标＝"_blank" rel="nofollow" href="//www.parkandroid.com/wiki/master-theorem/">主定理可用于求解闭形式解的递归关系。 递归关系有助于确定算法的效率。 使用分而治之的示例实现 这里有一个例子<一个目标＝"_blank" rel="nofollow" href="//www.parkandroid.com/wiki/merge/">归并排序， Python中的分治算法。 12 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合并（左，正确的）：结果＝［］left_idx，right_idx＝0，0而left_idx<len（左）和right_idx<len（正确的）：#改变这个比较的方向来改变排序的方向如果左［left_idx］＜＝正确的［right_idx]：结果．附加（左［left_idx]）left_idx+ =1其他的：结果．附加（正确的［right_idx]）right_idx+ =1如果左：结果．扩展（左［left_idx:])如果正确的：结果．扩展（正确的［right_idx:])返回结果defmerge_sort（米）：如果len（米）＜＝1：返回米中间＝len（米）//2左＝米[：中间］正确的＝米［中间：]左＝merge_sort（左）正确的＝merge_sort（正确的）返回列表（合并（左，正确的)） 这里有一个例子<一个目标＝"_blank" rel="nofollow" href="//www.parkandroid.com/wiki/binary-search/">二分查找， Python中的一个reduce and conquer算法。［1］ 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 defit_binarySearch（mylist，目标）：第一个＝0去年＝len（mylist）-1而第一个＜＝去年：中点＝（第一个+去年）/2如果mylist［中点］＝＝目标：返回中点其他的：如果目标<mylist［中点]：去年＝中点-1其他的：第一个＝中点+1返回没有一个test_list＝［0，3.，4，7，9，11，34，46，57，65］打印（it_binarySearch（test_list，4)）打印（it_binarySearch（test_list，30.)）打印（it_binarySearch（test_list，57)） 参考文献 ， .二叉搜索．检索日期:2016年4月1日<一个href="https://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html">http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html 引用:分而治之。Brilliant.org．检索从<一个href="//www.parkandroid.com/wiki/divide-and-conquer/">//www.parkandroid.com/wiki/divide-and-conquer/ 获得更多的辉煌。报名 报名阅读所有关于数学、科学和工程主题的维基和测验。 登陆Facebook<一个href="//www.parkandroid.com/account/google/login/?next=/wiki/divide-and-conquer/" id="login-google" class="btn btn-google signup-social ax-click" data-ax-id="clicked_login_from_problem_modal_google" data-ax-type="button" data-is_modal="true">使用谷歌登录<一个href="//www.parkandroid.com/account/login/?next=/wiki/divide-and-conquer/" id="problem-login-link" class="btn btn-email ax-click" data-ax-id="clicked_login_from_problem_modal_email" data-ax-type="button" data-is_modal="true" data-next="/wiki/divide-and-conquer/">用电子邮件登录 加入使用Facebook<一个href="//www.parkandroid.com/account/google/login/?next=/wiki/divide-and-conquer/" id="signup-google" class="btn btn-google signup-social ax-click" data-ax-id="clicked_signup_from_problem_modal_google" data-ax-type="button">加入使用谷歌<一个href="//www.parkandroid.com/account/signup/?signup=true&next=/wiki/divide-and-conquer/" id="signup-email" class="btn btn-email ax-click" data-ax-id="clicked_signup_from_problem_modal_email" data-ax-type="button" data-next="/wiki/divide-and-conquer/">加入使用电子邮件 忘记了密码?新用户?<一个href="//www.parkandroid.com/account/signup/?signup=true&next=/wiki/divide-and-conquer/" id="problem-signup-link-alternative" class="btn-link ax-click" data-ax-id="clicked_signup_from_problem_modal" data-ax-type="button" data-next="/wiki/divide-and-conquer/">报名 现有的用户?<一个href="//www.parkandroid.com/account/login/?next=/wiki/divide-and-conquer/" id="problem-login-link-alternative" class="btn-link ax-click" data-ax-id="clicked_login_from_problem_modal" data-ax-type="button" data-is_modal="true" data-next="/wiki/divide-and-conquer/">登录 × 问题加载… 注意加载… 设置加载…$