Review:DivideandConquer技术以及应用目录分治介绍分治案例动态规划介绍和案例分治、动态规划、贪心算法的区别贪心算法介绍和案例分治思想分治一共有三步：1.Divide：将待解决的问题分割成定义相同的子问题2.Conquer：将子问题逐个定义解决方案3.Combine：把每个子问题的解决方案结合，形成主问题的解决方案分治法所能解决的问题需要具备的特征：4.子问题之间相互独立5.子问题的解可以合并为原问题的解分治法可以降低解决方案的时间复杂度：比如，冒泡排序的时间复杂度是O(n2)，使用分治方法的时间复杂度是O(nlogn)。分治-二分查找(BinarySearch)［题目］给定一个n个元素的有序的（升序）整型数组nums和一个目标值target，搜索nums中是否存在目标值target，如果目标值存在返回下标，否则返回-1。示例1：输入：nums=[-1,0,3,5,9,12],target=9输出：4示例2：输入：nums=[-1,0,3,5,9,12],target=2输出：-13-195120[-1,0,3,5,9,12]由于查找次数等于二叉树的深度log₂n+1，所以算法时间复杂度为O(log₂n)。分治-二分查找(BinarySearch)defbinary_search(list,target):low=0high=len(list)-1#list中元素的数目whilelow<=high:mid=int((low+high)/2)#取中间元素的indexguess=list[mid]ifguess==target:#如果guess是要找的数字则返回midreturnmidelifguess>target:high=mid-1else:low=mid+1return-1如何优化划分？-插值查找前提：数组中每个元素的数值是均匀分布。如：key=9数组1：[0,1,2,3,4,5,6,7,8,9,10,11]可行数组2：[0,9,10,11]不可行基于二分查找的其他题目33.搜索旋转排序数组（中等）35.搜索插入位置（简单）50.pow(x,n)（中等）69.x的平方根（中等）74.搜索二维矩阵（中等）81.搜索旋转排序数组II（中等）153.寻找旋转排序数组中的最小值（中等）154.寻找旋转排序数组中的最小值II（难）分治-归并排序(MergeSort)时间复杂度为O(NlogN)分治-归并排序(MergeSort)defmerge_sort(lists):iflen(lists)<=1:returnlistsmiddle=len(lists)/2left=merge_sort(lists[:middle])right=merge_sort(lists[middle:])returnmerge(left,right)defmerge(a,b):c=[]h=j=0whilej
