算法学习--排序与查找

《算法学习--排序与查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法学习--排序与查找作者：qinzhaokun二分查找我们都知道二分查找算法，实际上二分查找以及其扩展应用是很广泛的。这里收集了一些和二分查找有关的有趣问题。强烈建议大家看完问题后最小化浏览器，先尝试自己去解决，然后再看代码，问题都不是太难。问题1描述给一个已经排序的数组，其中有N个互不相同的元素。要求使用最小的比较次数找出其中的一个元素。(你认为二分查找在排序数组里找一个元素是最优的算法的吗？)不需要太多的理论，这是一个典型的二分查找算法。先看下面的代码：intBinarySearch(intA[],intl,intr,intkey){intm;whi

2、le(l<=r){m=l+(r-l)/2;if(A[m]==key)//第一次比较returnm;if(A[m]key//边界:

3、r-l

4、=1//输入:A[l....r-1]intBinarySearch

5、(intA[],intl,intr,intkey){intm;while(r-l>1){m=l+(r-l)/2;if(A[m]<=key)l=m;elser=m;}if(A[l]==key)returnl;elsereturn-1在while循环中，我们仅依赖于一次比较。搜索空间(l->r)不断缩小，我们需要一个比较跟踪搜索状态。需要注意的，要保证我们恒等式（A[l]<=key&A[r]>key）正确，后面还会用到循环不变式。问题2描述给一个有N个互不相同的元素的已排序数组，返回小于或等于给定key的最大元素。例如输入为A={-1,2,3,5,6,8,9,

6、10} key=7,应该返回6.分析：我们可以用上面的优化方案，还是保持一个恒等式，然后移动左右两个指针。最终left指针会指向小于或等于给定key的最大元素(根据恒等式A[l]<=keyandA[r]>key)。->如果数组中所有元素都小于key，左边的指针left会一直移动到最后一个元素。->如果数组中所有元素都大于key，这是一个错误条件，无答案。->如果数组中的所有元素都<=key，这是最坏的情况根据下面的实现intFloor(intA[],intl,intr,intkey){intm;while(r-l>1){m=l+(r-l)/2;if(A[m

7、]<=key)l=m;elser=m;}returnA[l];}//初始调用intFloor(intA[],intsize,intkey){//如果keykeyintGet

8、RightPosition(intA[],intl,intr,intkey){intm;while(r-l>1){m=l+(r-l)/2;if(A[m]<=key)l=m;elser=m;}returnl;}//输入:数组区间(l...r]//恒等式:A[r]>=keyandA[l]>keyintGetLeftPosition(intA[],intl,intr,intkey){intm;while(r-l>1){m=l+(r-l)/2;if(A[m]>=key)r=m;elsel=m;}returnr;}intCountOccurances(intA[],

9、intsize,intkey){//找出边界intleft=GetLeftPosition(A,-1,size-1,key);intright=GetRightPosition(A,0,size,key);//key有可能不存在，需要判断return(A[left]==key&&key==A[right])?(right-left+1):0;问题4描述有一个已排序的数组（无相同元素）在未知的位置进行了旋转操作，找出在新数组中的最小元素所在的位置。例如：原数组{1,2,3,4,5,6,7,8,9,10}，旋转后的数组可能是{6,7,8,9,10,1,2,3,

10、4,5}，也可能是{8,9,10,1,2,3,4,5,6,7}分析