二分查找问题全集

二分查找问题全集1，原始二分查找题目：给定一个有序（非降序）数组A，求任意一个i使得A[i]等于target，不存在则返回-1例如：[2,4,6,8,9]找(4)位置11.1递归版[cpp]viewplaincopyprint?1.intbSearch(inta[],intlow,inthigh,inttarget){2.if(lowhigh)3.return-1;4.intmid=(low+high)/2;5.if(targeta[mid])6.returnbSearch(a,low,mid-1,target);7.elseif(targeta[mid])8.returnbSearch(a,mid+1,high,target);9.//if(target==a[mid])10.returnmid;11.}1.2迭代版[cpp]viewplaincopyprint?1.intsearch(intA[],intn,inttarget)2.{3.intlow=0,high=n-1;4.while(low=high)5.{6.//注意：若使用(low+high)/2求中间位置容易溢出7.intmid=low+((high-low)1);8.if(A[mid]==target)9.returnmid;10.elseif(A[mid]target)11.low=mid+1;12.else//A[mid]target13.high=mid-1;14.}15.return-1;16.}1.3返回插入位置给定一个有序（非降序）数组A，若target在数组中出现，返回位置，若不存在，返回它应该插入的位置。[cpp]viewplaincopyprint?1.intsearch(intA[],intn,inttarget)2.{3.intlow=0,high=n-1;4.while(low=high)5.{6.//注意：若使用(low+high)/2求中间位置容易溢出7.intmid=low+((high-low)1);8.if(A[mid]==target)9.returnmid;10.elseif(A[mid]target)11.low=mid+1;12.else//A[mid]target13.high=mid-1;14.}15.return-(low+1);16.}之所以返回-（low+1）而不是直接返回-low是因为low可能为0，如果直接返回-low就无法判断是正常返回位置0还是查找不成功返回的0。2，含重复元素，求=target的最小一个问题：给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1例如：A[2,4,6,8,8,8,9]求8得最小位置3[cpp]viewplaincopyprint?1.intsearch(intA[],intn,inttarget)2.{3.intlow=0,high=n-1;4.while(low=high)5.{6.//注意：若使用(low+high)/2求中间位置容易溢出7.intmid=low+((high-low)1);8.if(A[mid]==target)9.{10.if(mid0&&A[mid-1]==target)11.high=mid-1;12.else13.returnmid;14.}15.elseif(A[mid]target)16.low=mid+1;17.else//A[mid]target18.high=mid-1;19.}20.return-(low+1);21.}3，含重复元素，求=target的最大一个问题：给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]等于target，不存在则返回-1例如：A[2,4,6,8,8,8,9]求8得最大位置5[cpp]viewplaincopyprint?1.intsearch(intA[],intn,inttarget)2.{3.intlow=0,high=n-1;4.while(low=high)5.{6.//注意：若使用(low+high)/2求中间位置容易溢出7.intmid=low+((high-low)1);8.if(A[mid]==target)9.{10.if(midn-1&&A[mid+1]==target)11.low=mid+1;12.else13.returnmid;14.}15.elseif(A[mid]target)16.low=mid+1;17.else//A[mid]target18.high=mid-1;19.}20.return-(low+1);21.}4，含重复元素，求target的最大一个问题：给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]小于target，不存在则返回-1例如：A[2,4,6,8,8,8,9]求9得最大位置5问题转化：含重复元素，求2【=target的最小一个】的前一个。[cpp]viewplaincopyprint?1.intsearch(intA[],intn,inttarget)2.{3.intlow=0,high=n-1;4.while(low=high)5.{6.//注意：若使用(low+high)/2求中间位置容易溢出7.intmid=low+((high-low)1);8.if(A[mid]==target)9.{10.if(mid0&&A[mid-1]==target)11.high=mid-1;12.else13.return(mid==0)?-1:mid-1;14.}15.elseif(A[mid]target)16.low=mid+1;17.else//A[mid]target18.high=mid-1;19.}20.return-(low+1);21.}5，含重复元素，求target的最小一个问题：给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]大于target，不存在则返回-1例如：A[2,4,6,8,8,8,9]求6的最小位置3问题转化：含重复元素，求3【=target的最大一个】的后一个。[cpp]viewplaincopyprint?1.intsearch(intA[],intn,inttarget)2.{3.intlow=0,high=n-1;4.while(low=high)5.{6.//注意：若使用(low+high)/2求中间位置容易溢出7.intmid=low+((high-low)1);8.if(A[mid]==target)9.{10.if(midn-1&&A[mid+1]==target)11.low=mid+1;12.else13.return(mid==n-1)?-n:mid+1;14.}15.elseif(A[mid]target)16.low=mid+1;17.else//A[mid]target18.high=mid-1;19.}20.return-(low+1);21.}6，含重复元素，求=target的出现次数问题：给定一个有序（非降序）数组A，可含有重复元素，求target在数组中出现的次数。例如：A[2,4,6,8,8,8,9]求8的出现次数3求出第一次出现位置和最后一次出现位置。由于前面都已实现，这里不多解释。请参考实现代码与注释[cpp]viewplaincopyprint?1.intcount(intA[],intn,inttarget)2.{3.intfirstPos=searchFirstPos(A,n,target);//第一次出现位置4.if(firstPos==-1)5.return0;6.intlastPos=searchLastPos(A,n,target);//最后一次出现位置7.returnlastPos-firstPos+1;//出现次数8.}7，含重复元素，求绝对值最小的元素问题：给定一个有序（非降序）数组A，可含有重复元素，求绝对值最小的元素的位置例如：A[-4,-2,-1,2,3,8,9]求结果为2[cpp]viewplaincopyprint?1.intsearchMinAbs(intA[],intn)2.{3.intlow=0,high=n-1;4.while(lowhigh)5.{6.intmid=low+((high-low)1);7.if(A[mid]0)8.low=mid+1;9.else//A[mid]=010.high=mid;11.}12./*循环结束时，如果low!=n-1，A[low]=0，如果low0，A[low-1]0*/13.if(low0&&abs(A[low-1])abs(A[low]))14.returnlow-1;15.else16.returnlow;17.}8，问题：给定一个有序（非降序）数组A和一个有序（非降序）数组B，可含有重复元素，求两个数组合并结果中的第k(k=0)个数字。这个题目出现了两个数组，有序的，不管怎样我们就应该首先考虑二分查找是否可行。若使用顺序查找，时间复杂度最低为O(k)，就是类似归并排序中的归并过程。使用用二分查找时间复杂度为O(logM+logN)。二分查找的具体实现过程请参考实现代码与注释。[cpp]viewplaincopyprint?1.intfindKthIn2SortedArrays(intA[],intm,intB[],intn,intk)2.{3.if(m=0)//数组A中没有元素，直接在B中找第k个元素4.returnB[k];5.if(n=0)//数组B中没有元素，直接在A中找第k个元素6.returnA[k];7.inti=(m-1)1;//数组A的中间位置8.intj=(n-1)1;//数组B的中间位置9.if(A[i]=B[j])//数组A的中间元素小于等于数组B的中间元素10.{11./*12.设x为数组A和数组B中小于B[j]的元素数目，则i+1+j+1小于等于x，13.因为A[i+1]到A[m-1]中还可能存在小于等于B[j]的元素；14.如果k小于i+1+j+1，那么要查找的第k个元素肯定小于等于B[j]，15.因为x大于等于i+1+j+1；既然第k个元素小于等于B[j]，那么只16.需要在A[0]~A[m-1]和B[0]~B[j]中查找第k个元素即可，递归调用下去。17.*/18.if(ki+1+j+1)19.{20.if(j0)21.returnfindKthIn2SortedArrays(A,m,B,j+1,k);22.else//j==0时特殊处理，防止死循环23.{24.if(k==0)25.returnmin(A[0],B[0]);26.if(k==m)27.returnmax(A[m-1],B[0]);28.returnA[k]B[0]?A[k]:max(A[k-1],B[0]);29.}30.}31./*32.设y为数组A和数组B中小于于等于A[i]的元素数目，则i+1+j+1大于等于y；33.如果k大于等于i+1+j+1，那么要查找到第k个元素肯定大于A[i]，因为34.i+1+j+1大于等于y；既然第k个元素大于A[i]，那么只需要在A[i+1]~A[m-1]35.和B[0]~B[n-1]中查找第k-i-1个元素，递归调用下去。36.*/37.else38.returnfindKthIn2SortedArrays(A+i+1,m-i-1,B,n,k-i-1);39.}40.//如果数组A的中间元素大于数组B的中间元素，那么交换数组A和B，重新调用即可41.else42.returnfindKthIn2SortedArrays(B,n,A,m,k);43.}9问题：一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转