二分查找问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
全集1，原始二分查找题目：给定一个有序（非降序）数组A，求任意一个i使得A[i]等于target，不存在则返回-1例如：[2,4,6,8,9]找(4)位置11.1递归版[cpp]viewplaincopyprint?1.intbSearch(inta[],intlow,inthigh,inttarget){if(low>high)return-1;4.intmid=(low+high)/2;if(target
a[mid])returnbSearch(a,mid+1,high,target);//if(target==a[mid])returnmid;}1.2迭代版[cpp]viewplaincopyprint?1.intsearch(intA[],intn,inttarget){3.intlow=0,high=n-1;while(low<=high){6.//注意：若使用(low+high)/2求中间位置容易溢出7.intmid=low+((high-low)>>1);if(A[mid]==target)returnmid;elseif(A[mid]targethigh=mid-1;}return-1;}1.3返回插入位置给定一个有序（非降序）数组A，若target在数组中出现，返回位置，若不存在，返回它应该插入的位置。[cpp]viewplaincopyprint?1.intsearch(intA[],intn,inttarget){3.intlow=0,high=n-1;while(low<=high){6.//注意：若使用(low+high)/2求中间位置容易溢出7.intmid=low+((high-low)>>1);if(A[mid]==target)returnmid;elseif(A[mid]targethigh=mid-1;}return-(low+1);}之所以返回-（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){3.intlow=0,high=n-1;while(low<=high){6.//注意：若使用(low+high)/2求中间位置容易溢出7.intmid=low+((high-low)>>1);if(A[mid]==target){if(mid>0&&A[mid-1]==target)11.high=mid-1;else13.returnmid;}elseif(A[mid]targethigh=mid-1;}return-(low+1);}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){3.intlow=0,high=n-1;while(low<=high){6.//注意：若使用(low+high)/2求中间位置容易溢出7.intmid=low+((high-low)>>1);if(A[mid]==target){if(midtargethigh=mid-1;}return-(low+1);}4，含重复元素，求>1);if(A[mid]==target){if(mid>0&&A[mid-1]==target)11.high=mid-1;else13.return(mid==0)?-1:mid-1;}elseif(A[mid]targethigh=mid-1;}return-(low+1);}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){3.intlow=0,high=n-1;while(low<=high){6.//注意：若使用(low+high)/2求中间位置容易溢出7.intmid=low+((high-low)>>1);if(A[mid]==target){if(midtargethigh=mid-1;}return-(low+1);}6，含重复元素，求=target的出现次数问题：给定一个有序（非降序）数组A，可含有重复元素，求target在数组中出现的次数。例如：A[2,4,6,8,8,8,9]求8的出现次数3求出第一次出现位置和最后一次出现位置。由于前面都已实现，这里不多解释。请参考实现代码与注释[cpp]viewplaincopyprint?1.intcount(intA[],intn,inttarget){3.intfirstPos=searchFirstPos(A,n,target);//第一次出现位置if(firstPos==-1)return0;6.intlastPos=searchLastPos(A,n,target);//最后一次出现位置7.returnlastPos-firstPos+1;//出现次数}7，含重复元素，求绝对值最小的元素问题：给定一个有序（非降序）数组A，可含有重复元素，求绝对值最小的元素的位置例如：A[-4,-2,-1,2,3,8,9]求结果为2[cpp]viewplaincopyprint?1.intsearchMinAbs(intA[],intn){3.intlow=0,high=n-1;while(low>1);if(A[mid]<0)low=mid+1;else//A[mid]>=0high=mid;}12./*循环结束时，如果low!=n-1，A[low]>=0，如果low>0，A[low-1]<0*/if(low>0&&abs(A[low-1])=0)个数字。这个题目出现了两个数组，有序的，不管怎样我们就应该首先考虑二分查找是否可行。若使用顺序查找，时间复杂度最低为O(k)，就是类似归并排序中的归并过程。使用用二分查找时间复杂度为O(logM+logN)。二分查找的具体实现过程请参考实现代码与注释。[cpp]viewplaincopyprint?1.intfindKthIn2SortedArrays(intA[],intm,intB[],intn,intk){3.if(m<=0)//数组A中没有元素，直接在B中找第k个元素returnB[k];5.if(n<=0)//数组B中没有元素，直接在A中找第k个元素returnA[k];7.inti=(m-1)>>1;//数组A的中间位置8.intj=(n-1)>>1;//数组B的中间位置9.if(A[i]<=B[j])//数组A的中间元素小于等于数组B的中间元素{/*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个元素即可，递归调用下去。*/if(k0)21.returnfindKthIn2SortedArrays(A,m,B,j+1,k);22.else//j==0时特殊处理，防止死循环{24.if(k==0)25.returnmin(A[0],B[0]);26.if(k==m)27.returnmax(A[m-1],B[0]);28.returnA[k]>1);if(A[mid]==target)returnmid;if(A[mid]>=A[low]){11.//low~mid是升序的if(target>=A[low]&&targetA[mid]&&target<=A[high])21.low=mid+1;else23.high=mid-1;}}return-1;}如果这样的数组中存在重复元素，还能使用二分吗？答案是不能。请看几个例子[1,2,2,2,2],[2,1,2,2,2],[2,2,1,2,2],[2,2,2,1,2],[2,2,2,2,1]这些都是有第一个数组旋转一次变化来的，我们不能通过二分确定是否存在元素1.，问题：一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求最小值所在位置如果中间元素小于左端元素，则最小值在左半区间内（包含中间元素）；右端元素，则最小值在右半区间内（包含中间元素）。请参考实现代码与注释。如果中间元素大于[cpp]viewplaincopyprint?1.intsearchMinInRotatedArray(intA[],intn){if(n==1)return0;5.intlow=0,high=n-1;6.while(low>1);9.if(A[mid]A[low],//最小值在mid和high之间low=mid;}returnA[low]0)小元素的位置我们可以利用上一题的解答，求出最小值所在位置后，便可以求出第k小元素。请参考实现代码与注释[cpp]viewplaincopyprint?1.intsearchKthInRotatedArray(intA[],intn,intk){3.intposMin=searchMinInRotatedArray(A,n);return(posMin+k-1)%n;}12，查找旋转数组的最小数字题目：即找分界点，比如34512，返回的是位置3。以题目中的旋转数组为例，{3,4,5,1,2}，我们可以有序数组经过旋转以后被分割为两段有序的数组，比如此处被分为{3,4,5}{1,2}这样连个数组，并且前半段数组中的数字肯定大于等于后半段的数组。我们找中间元素a[mid]，让其跟元素首元素a[low]和尾元素a[high]比较，如果大于首元素a[low]，则中间元素属于前半段有序数组；如果小于尾元素a[high]，那么中间元素就是后半段的元素。这里我们设定两个指针start和end分别指向数组的首尾元素，然后当start指向前半段最后一个元素，end指向后半段第一个元素，这是程序就找到了数组中的最小元素，就是end指向的那个数，程序的出口就是end-start==1。[cpp]viewplaincopyprint?1.intbSearchMinValue(inta[],intlow,inthigh){2.//终止递归条件是low和high差1，原因是后面mid都不是+1-1处理的if(low+1==high)returnhigh;5.intmid=(low+high)/2;6.7.if(a[mid]>a[low])//左侧有序，在右边找分界点returnbSearchMinValue(a,mid,high);9.if(a[mid]a[left],则right=mid-1；其他情况，left=mid+1；如果右边是有序的，若target>a[mid]且target=a[low]){//左侧有序，在右边有分界点11.//在左侧有序的之中if(target>=a[low]&&targeta[mid]&&target<=a[high])returnbSearchMinValue(a,mid+1,high,target);//在左侧有分界点之中elsereturnbSearchMinValue(a,low,mid-1,target);}return-1;}
浙公网安备 33021202002483