二分查找问题全集

1、二分查找问题全集1,原始二分查找题目：给定一个有序(非降序)数组A,求任意一个i使彳导Ai等于target,不存在则返回-1例如：2,4,6,8,9找(4)位置11.1 递归版cppviewplaincopyprint?1. intbSearch(inta,intlow,inthigh,inttarget)2. if(lowhigh)3. return-1;4. intmid=(low+high)/2;5. if(targetamid)8. returnbSearch(a,mid+1,high,target);9. /if(target=amid)10. returnmid;11. 1.2 迭

2、代版cppviewplaincopyprint?1. intsearch(intA,intn,inttarget)2. 3. intlow=0,high=n-1;4. while(low1);8. if(Amid=target)9. returnmid;10. elseif(Amidtarget13. high=mid-1;14. 15. return-1;16. 1.3 返回插入位置给定一个有序(非降序)数组A,若target在数组中出现，返回位置，若不存在，返回它应该插入的位置。cppviewplaincopyprint?1. intsearch(intA,intn,inttarget)2

3、. 3. intlow=0,high=n-1;4. while(low1);8. if(Amid=target)9. returnmid;10. elseif(Amidtarget13. high=mid-1;14. 15. return-(low+1);16. 之所以返回-(low+1)而不是直接返回-low是因为low可能为0,如果直接返回-low就无法判断是正常返回位置0还是查找不成功返回的0。2,含重复元素，求=target的最小一个问题：给定一个有序(非降序)数组A,可含有重复元素，求最小的i使得Ai等于target,不存在则返回-1例如：A2,4,6,8,8,8,9求8得最小位置3

4、cppviewplaincopyprint?1. intsearch(intA,intn,inttarget)2. 3. intlow=0,high=n-1;4. while(low1);8. if(Amid=target)9. 10. if(mid0&Amid-1=target)11. high=mid-1;12. else13. returnmid;14. 15. elseif(Amidtarget18. high=mid-1;19. 20. return-(low+1);21. 3,含重复元素，求=target的最大一个问题：给定一个有序(非降序)数组A,可含有重复元素，求最大的i使得A

5、i等于target,不存在则返回-1例如：A2,4,6,8,8,8,9求8得最大位置5cppviewplaincopyprint?1. intsearch(intA,intn,inttarget)2. 3. intlow=0,high=n-1;4. while(low1);8. if(Amid=target)9. 10. if(midn-1&Amid+1=target)11. low=mid+1;12. else13. returnmid;14. 15. elseif(Amidtarget18. high=mid-1;19. 20. return-(low+1);21. 4,含重复元素，求ta

6、rget的最大一个问题：给定一个有序(非降序)数组A,可含有重复元素，求最大的i使得Ai小于target,不存在则返回-1例如：A2,4,6,8,8,8,9求9得最大位置5问题转化：含重复元素，求2=target的最小一个】的前一个。cppviewplaincopyprint?1. intsearch(intA,intn,inttarget)2. (3. intlow=0,high=n-1;4. while(low1);8. if(Amid=target)9. (10. if(mid0&Amid-1=target)11. high=mid-1;12. else13. return(mid=0)

7、?-1:mid-1;14. 15. elseif(Amidtarget18. high=mid-1;19. 20. return-(low+1);21.5,含重复元素，求target的最小一个问题：给定一个有序(非降序)数组A,可含有重复元素，求最小的i使得Ai大于target,不存在则返回-1例如：A2,4,6,8,8,8,9求6的最小位置3问题转化：含重复元素，求3=target的最大一个】的后一个。cppviewplaincopyprint?1. intsearch(intA,intn,inttarget)2. (3. intlow=0,high=n-1;4. while(low1);8

8、. if(Amid=target)9. (10. if(midn-1&Amid+1=target)11. low=mid+1;12. else13. return(mid=n-1)?-n:mid+1;14. 15. elseif(Amidtarget18. high=mid-1;19. 20. return-(low+1);21. 6,含重复元素，求=target的出现次数问题：给定一个有序(非降序)数组A,可含有重复元素，求target在数组中出现的次数。例如：A2,4,6,8,8,8,9求8的出现次数3求出第一次出现位置和最后一次出现位置。由于前面都已实现，这里不多解释。请参考实现代码与注

9、释cppviewplaincopyprint?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求

10、结果为2cppviewplaincopyprint?1. intsearchMinAbs(intA,intn)2. 3. intlow=0,high=n-1;4. while(low1);7. if(Amid=010. high=mid;11. 12. /*循环结束时，如果low!=n-1,Alow=0,如果low0,Alow-10&abs(Alow-1)=0)个数字。这个题目出现了两个数组，有序的，不管怎样我们就应该首先考虑二分查找是否可行。若使用顺序查找，时间复杂度最低为O(k),就是类似归并排序中的归并过程。使用用二分查找时间复杂度为O(logM+logN)。二分查找的具体实现过程请参考

11、实现代码与注释。cppviewplaincopyprint?1.intfindKthIn2SortedArrays(2. .7.8.9.if(m=0)/数组A中没有元素，直接在B中找第k个元素returnBk;if(n1;/intj=(n-1)1;/if(Ai=Bj)/数组A的中间位置数组B的中间位置数组A的中间元素小于等于数组B的中间元素intA,intm,intB,intn,intk)4./*设x为数组A和数组B中小于Bj的元素数目

12、，则i+1+j+1小于等于x,因为Ai+1到Am-1中还可能存在小于等于Bj的元素；如果k小于i+1+j+1,那么要查找的第k个元素肯定小于等于Bj,因为x大于等于i+1+j+1;既然第k个元素小于等于Bj,那么只需要在A0Am-1和B0Bj中查找第k个元素即可，递归调用下去。*/if(k0)returnfindKthIn2SortedArrays(A,m,B,j+1,k);else/j=0时特殊处理，防止死循环if(k=0)returnmin(A0,B0);if(k=m)returnmax(Am-1,B0);returnAkB0?Ak:max(Ak-1,B0);)/*设y为数组A和数组B中小

13、于于等于Ai的元素数目，则i+1+j+1大于等于y;如果k大于等于i+1+j+1,那么要查找到第k个元素肯定大于Ai,因为i+1+j+1大于等于y;既然第k个元素大于Ai,那么只需要在Ai+1Am-135. 和B0Bn-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

14、. 9问题：一个有序(升序)数组，没有重复元素，在某一个位置发生了旋转后，求target在变化后的数组中出现的位置，不存在则返回-1如0124567可能变成4567012我们先比较中间元素是否是目标值，如果是返回位置。如果不是，我们就应该想办法将搜索区间减少一半。因为存在旋转变化，所以我们要多做一些判断。我们知道因为只有一次旋转变化，所以中间元素两边的子数组肯定有一个是有序的，那么我们可以判断target是不是在这个有序的子数组中，从而决定是搜索这个子数组还是搜索另一个子数组。具体请参考实现代码与注释。cppviewplaincopyprint?1. intsearchInRotatedArr

15、ay(intA,intn,inttarget)2. 3. intlow=0,high=n-1;4. while(low1);7. if(Amid=target)8. returnmid;9. if(Amid=Alow)10. 11. /lowmid是升序的12. if(target=Alow&targetAmid&target=Ahigh)21. low=mid+1;22. else23. high=mid-1;24. 25. 26. return-1;27. 如果这样的数组中存在重复元素，还能使用二分吗？答案是不能。请看几个例子1,2,2,2,2,2,1,2,2,2,2,2,1,2,2,2,

16、2,2,1,2,2,2,2,2,1这些都是有第一个数组旋转一次变化来的，我们不能通过二分确定是否存在元素1.10,问题：一个有序(升序)数组，没有重复元素，在某一个位置发生了旋转后，求最小值所在位置如果中间元素小于左端元素，则最小值在左半区间内(包含中间元素)；如果中间元素大于右端元素，则最小值在右半区间内(包含中间元素)。请参考实现代码与注释。cppviewplaincopyprint?1. intsearchMinInRotatedArray(intA,intn)2. 3. if(n=1)4. return0;5. intlow=0,high=n-1;6. while(low1);9. i

17、f(AmidAlow,/最小值在mid和high之间12. low=mid;13. 14. returnAlow0)小元素的位置我们可以利用上一题的解答，求出最小值所在位置后，便可以求出第k小元素。请参考实现代码与注释cppviewplaincopyprint?1. intsearchKthInRotatedArray(intA,intn,intk)2. (3. intposMin=searchMinInRotatedArray(A,n);4. return(posMin+k-1)%n;5. 12,查找旋转数组的最小数字题目：即找分界点，比如34512,返回的是位置3。以题目中的旋转数组为例，

18、3,4,5,1,2,我们可以有序数组经过旋转以后被分割为两段有序的数组，比如此处被分为3,4,51,2这样连个数组，并且前半段数组中的数字肯定大于等于后半段的数组。我们找中间元素amid,让其跟元素首元素alow和尾元素ahigh比较，如果大于首元素alow,则中间元素属于前半段有序数组；如果小于尾元素ahigh,那么中间元素就是后半段的元素。这里我们设定两个指针start和end分别指向数组的首尾元素，然后当start指向前半段最后一个元素，end指向后半段第一个元素，这是程序就找到了数组中的最小元素，就是end指向的那个数，程序的出口就是end-start=1。cppviewplaincopyprint?1. intbSearchMinValue(inta,intlow,inthigh)2. /终止递归条件是low和high差1,原因是后面mid都不是+1-1处理的3. if(low+1=high)4. returnhigh;5. intmid=(low+high)/2;6.7. if(amidalow)/左侧有序，在右边找分界点8. returnbSearchMinValue(a,mid,high);9. if(amidahigh)/右侧有序，在左