15.binary search及扩展出来的几个问题讨论.doc

binary search及扩展出来的几个问题讨论 简介 ? ? binary search是一个几乎大家耳熟能详的问题，只要一提到这个问题，似乎立马就有人把代码都浮现在头脑里了。它本质上就是通过不断的折半查找来缩小范围，这样可以达到一个很理想的运行效率。这个方法本身有几个小的地方值得注意。另外，通过binary search引申出来的一些问题也是各种各样，这里也针对两个比较有意思的问题做了一点分析。 ? ? 如果用一个比较简单直白的语言来介绍binary search的话，无非就是在一个已经排好序的数组里，通过每次将元素的中间值和目标元素来比较，如果中间值大的话，则在前面部分范围内继续查找，否则在后面的部分继续查找。每次求的这个中位数就将数组分成了两半。这样后面每次查找的范围也就缩小了。假设一个数组的元素有n个，每次执行一个折半元素范围就减少一半。从直观上来看，顶多lgN次的折半也就得到一个结果了。所以，binary search方法的时间复杂度为lgn。 ? ? 下面是binary search的两个实现： Java代码?? public?static?int?search(int[]?a,?int?val)?? {?? ????int?start?=?0;?? ????int?end?=?a.length?-?1;?? ????int?middle;?? ????while(start?=?end)?? ????{?? ????????middle?=?start?+?(end?-?start)?/?2;?? ????????if(val??a[middle])?? ????????{?? ????????????start?=?middle?+?1;?? ????????}?? ????????else?if(val??a[middle])?? ????????{?? ????????????end?=?middle?-?1;?? ????????}?? ????????else?? ????????????return?middle;?? ????}?? ?? ????return?-1;?? }?? ?? public?static?int?recSearch(int[]?a,?int?start,?int?end,?int?val)?? {?? ????if(start??end)?? ????????return?-1;?? ?? ????int?middle?=?start?+?(end?-?start)?/?2;?? ????if(val?==?a[middle])?? ????????return?middle;?? ????else?if(val??a[middle])?? ????????return?recSearch(a,?middle?+?1,?end,?val);?? ????else?? ????????return?recSearch(a,?start,?middle?-?1,?val);?? }?? ? ? 看这些具体的代码，实际上有几个细节是很值得注意的。1. 我们在while循环里面比较的条件是start = end。 这里一定要把等于的情况也考虑进去。因为有可能在有哪些信誉好的足球投注网站到start == end这一步，我们还是需要判断一下是否和结果相等，否则会漏掉这么一种特殊的情况。2. 在求两个数start, end的中位数的时候，一般我们会笼统的用(start + end) / 2这种方式。但是，在数字比较大的情况下，如果start + end Integer.MAX_VALUE的话，则会使得首先括号里的运算产生溢出，进而产生不正确的结果。所以为了避免这种情况需要使用start + (end - start) / 2。 ? 引申出来的几个问题 ? ? 可以说，前面讨论的binary search没什么新奇的，最不济细心看看也就都弄明白了。可是如果在这个问题的基础上结合一些其他情况引申出来的问题，事情就会复杂很多： ? ? 前面我们讨论的binary search是基于所有的元素都是排好序的情况，而且一般是从小到大的顺序。现在考虑一种特殊情况，如果我们有一部分元素循环移位了k个位置，那么和原来的顺序比较可能会有如下的结果： ? ? ?现在，在这种情况下，如果我们也期望达到logn的元素查找效果的话，该怎么去做呢？根据上图的描述，如果我们将一个递增的数组循环移位若干位的时候，它将会变成一个由两个递增的序列组成的数组。在这两个序列中间是由一个最大值和最小值作为间隔隔开，好像突然间冒出来的一个坎。由于这么个移位，我们如果取数组中间值mid的时候，它可能落在前面那个递增的串上也可能落在后面那个递增的串上