分治算法二分搜索技术

1、分治算法(一)二分搜索技术分治算法的本质就是将一个大规模的问题分解为若干个小规模的相同子问题，分而治之。分治算法简述1.1分治算法也有它的适用条件，满足以下3个条件，才能使用分治法来解决：原问题可分解为若干个规模较小的相同子问题子问题相互独立子问题的解可以合并为原问题的解1.2使用分治法解题的步骤：分解：将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。治理：对子问题进行求解。合并：按原问题的要求，将子问题的解逐层合并构成原问题的解。用二分搜索技术玩猜数字游戏2.1问题描述假如你女朋友想跟你玩一个游戏，说：“亲爱的，猜一下我心里想的是哪个数字？这个数字在110范围内。”你

2、可能会猜1,女朋友说：“小了。”接着你猜2,女朋友说：“小了。”接着你又猜3,女朋友还是说：“小了。”这时候女朋友会很无奈地说：“天呐，你怎么可以这么笨！”这样每次加1的方法来猜，如果给定的数字是1,那么很幸运，一次就能猜中；但是如果给定的是10,用这种方法就需要猜10次。推广开来，如果是n个数，使用这种方法最坏的情况要猜n次才能成功。如何能够用最少次数猜中给定的数字？我们的二分查找(也叫折半查找)可以很好地解决这个问题。就拿上面问题为例，因为这些数字(1到10)是有序(升序)的，使用二分查找每次和中间元素比较，如果提示说猜的数字比给定的数字小了，即给定数字比中间元素大，则在后半部分查找；如果

3、提示说猜的数字比给定的数字大了，即给定数字比中间元素小,则在前半部分查找。这样每次查找,问题都会缩小为上次问题规模的一半,所以也被称为折半查找。2.2算法设计用列表num存储该有序序列(假定为升序)，设变量low表示查找范围的下界，high表示查找范围的上界，middle表示查找范围的中间位置，x为特定的查找元素。初始化。令low=0,即指向有序列表num的第一个元素(列表元素下标从0开始)；high=n-1,即指向有序列表num的最后一个元素,n表示列表长度，也就是列表元素的个数。middle=(low+high)/2,即指向查找范围的中间元素(low+high)为奇数的话，除以2并不能得到

4、整数，但是列表中元素的下标都是整数,这里实际上是向下取整,比如：3.5向下取整为3。判定lownummiddle,令low=middle+1;如果xnummiddle,令high=middle-1,转为第2步。2.3算法实现(1)非递归实现numList=#定义一个计数变量，统计查找次数count=1defBinarySearch(numList,x):low=0high=len(numList)-1globalcountwhile(low=high):#地板除向下取整middle=(low+high)/2ifx=numListmiddle:#指定元素等于中间元素，查找成功，返回元素下标returnmiddleelifxhigh:returnNonemiddle=(low+high)/2ifx=numListmiddle:returnmiddleelifxnumListmiddle:returnrecusionBS(numList,x,low,middle-1)else:returnrecusionBS(numList,x,middle+1