1，原始二分查找

题目：给定一个有序（非降序）数组A，求任意一个i使得A[i]等于target，不存在则返回-1

例如：[2,4,6,8,9]找(4) 位置1

1.1 递归版

[cpp]

intbSearch(inta[],intlow,inthigh,inttarget){ if(low>high) return-1; intmid=(low+high)/2; if(target returnbSearch(a,low,mid-1,target); elseif(target>a[mid]) returnbSearch(a,mid+1,high,target); //if(target==a[mid]) returnmid; }

1.2 迭代版

[cpp]

intsearch(intA[],intn,inttarget) { intlow=0,high=n-1; while(low<=high) { //注意：若使用(low+high)/2求中间位置容易溢出 intmid=low+((high-low)>>1); if(A[mid]==target) returnmid; elseif(A[mid]<target) low=mid+1; else//A[mid]>target high=mid-1; } return-1; }

1.3 返回插入位置

给定一个有序（非降序）数组A，若target在数组中出现，返回位置，若不存在，返回它应该插入的位置。

[cpp]

intsearch(intA[],intn,inttarget) { intlow=0,high=n-1; while(low<=high) { //注意：若使用(low+high)/2求中间位置容易溢出 intmid=low+((high-low)>>1); if(A[mid]==target) returnmid; elseif(A[mid]<target) low=mid+1; else//A[mid]>target high=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]

intsearch(intA[],intn,inttarget) { intlow=0,high=n-1; while(low<=high) { //注意：若使用(low+high)/2求中间位置容易溢出 intmid=low+((high-low)>>1); if(A[mid]==target) { if(mid>0&&A[mid-1]==target) high=mid-1; else returnmid; } elseif(A[mid]<target) low=mid+1; else//A[mid]>target high=mid-1; } return-(low+1); }

3，含重复元素，求=target的最大一个

问题：给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]等于target，不存在则返回-1

例如：A[2,4,6,8,8,8,9]求8得最大位置5

[cpp]

intsearch(intA[],intn,inttarget) { intlow=0,high=n-1; while(low<=high) { //注意：若使用(low+high)/2求中间位置容易溢出 intmid=low+((high-low)>>1); if(A[mid]==target) { if(mid<n-1&&A[mid+1]==target) low=mid+1; else returnmid; } elseif(A[mid]<target) low=mid+1; else//A[mid]>target high=mid-1; } return-(low+1); }

4，含重复元素，求

问题：给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]小于target，不存在则返回-1

例如：A[2,4,6,8,8,8,9]求9得最大位置5

问题转化：含重复元素，求2【=target的最小一个】的前一个。

[cpp]

intsearch(intA[],intn,inttarget) { intlow=0,high=n-1; while(low<=high) { //注意：若使用(low+high)/2求中间位置容易溢出 intmid=low+((high-low)>>1); if(A[mid]==target) { if(mid>0&&A[mid-1]==target) high=mid-1; else return(mid==0)?-1:mid-1; } elseif(A[mid]<target) low=mid+1; else//A[mid]>target high=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]

intsearch(intA[],intn,inttarget) { intlow=0,high=n-1; while(low<=high) { //注意：若使用(low+high)/2求中间位置容易溢出 intmid=low+((high-low)>>1); if(A[mid]==target) { if(mid<n-1&&A[mid+1]==target) low=mid+1; else return(mid==n-1)?-n:mid+1; } elseif(A[mid]<target) low=mid+1; else//A[mid]>target high=mid-1; } return-(low+1); }

6，含重复元素，求=target的出现次数

问题：给定一个有序（非降序）数组A，可含有重复元素，求target在数组中出现的次数。

例如：A[2,4,6,8,8,8,9]求8的出现次数3

求出第一次出现位置和最后一次出现位置。由于前面都已实现，这里不多解释。请参考实现代码与注释

[cpp]

intcount(intA[],intn,inttarget) { intfirstPos=searchFirstPos(A,n,target);//第一次出现位置 if(firstPos==-1) return0; intlastPos=searchLastPos(A,n,target);//最后一次出现位置 returnlastPos-firstPos+1;//出现次数 }

7，含重复元素，求绝对值最小的元素

问题：给定一个有序（非降序）数组A，可含有重复元素，求绝对值最小的元素的位置

例如：A[-4,-2,-1,2,3,8,9]求结果为2

[cpp]

intsearchMinAbs(intA[],intn) { intlow=0,high=n-1; while(low<high) { intmid=low+((high-low)>>1); if(A[mid]<0) low=mid+1; else//A[mid]>=0 high=mid; } if(low>0&&abs(A[low-1])<abs(A[low])) returnlow-1; else returnlow; }

8，

问题：给定一个有序（非降序）数组A和一个有序（非降序）数组B，可含有重复元素，求两个数组合并结果中的第k(k>=0)个数字。

这个题目出现了两个数组，有序的，不管怎样我们就应该首先考虑二分查找是否可行。若使用顺序查找，时间复杂度最低为O(k)，就是类似归并排序中的归并过程。使用用二分查找时间复杂度为O(logM+logN)。二分查找的具体实现过程请参考实现代码与注释。

[cpp]

intfindKthIn2SortedArrays(intA[],intm,intB[],intn,intk) { if(m<=0)//数组A中没有元素，直接在B中找第k个元素 returnB[k]; if(n<=0)//数组B中没有元素，直接在A中找第k个元素 returnA[k]; inti=(m-1)>>1;//数组A的中间位置 intj=(n-1)>>1;//数组B的中间位置 if(A[i]<=B[j])//数组A的中间元素小于等于数组B的中间元素 { if(k<i+1+j+1) { if(j>0) returnfindKthIn2SortedArrays(A,m,B,j+1,k); else//j==0时特殊处理，防止死循环 { if(k==0) returnmin(A[0],B[0]); if(k==m) returnmax(A[m-1],B[0]); returnA[k]<B[0]?A[k]:max(A[k-1],B[0]); } } else returnfindKthIn2SortedArrays(A+i+1,m-i-1,B,n,k-i-1); } //如果数组A的中间元素大于数组B的中间元素，那么交换数组A和B，重新调用即可 else returnfindKthIn2SortedArrays(B,n,A,m,k); }

9

问题：

一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求target在变化后的数组中出现的位置，不存在则返回-1

如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2

我们先比较中间元素是否是目标值，如果是返回位置。如果不是，我们就应该想办法将搜索区间减少一半。因为存在旋转变化，所以我们要多做一些判断。我们知道因为只有一次旋转变化，所以中间元素两边的子数组肯定有一个是有序的，那么我们可以判断target是不是在这个有序的子数组中，从而决定是搜索这个子数组还是搜索另一个子数组。具体请参考实现代码与注释。

[cpp]

intsearchInRotatedArray(intA[],intn,inttarget) { intlow=0,high=n-1; while(low<=high) { intmid=low+((high-low)>>1); if(A[mid]==target) returnmid; if(A[mid]>=A[low]) { //low~mid是升序的 if(target>=A[low]&&target<A[mid]) high=mid-1; else low=mid+1; } else { //mid~high是升序的 if(target>A[mid]&&target<=A[high]) low=mid+1; else 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.

10，

问题：一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求最小值所在位置

如果中间元素小于左端元素，则最小值在左半区间内（包含中间元素）；如果中间元素大于右端元素，则最小值在右半区间内（包含中间元素）。请参考实现代码与注释。

[cpp]

intsearchMinInRotatedArray(intA[],intn) { if(n==1) return0; intlow=0,high=n-1; while(low<high-1)//保证mid!=low且mid!=high { intmid=low+((high-low)>>1); if(A[mid]<A[low])//最小值在low~mid high=mid; else//A[mid]>A[low],//最小值在mid和high之间 low=mid; } returnA[low]<A[low+1]?low:low+1; }

11,

问题：

一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求第k(k > 0)小元素的位置

我们可以利用上一题的解答，求出最小值所在位置后，便可以求出第k小元素。请参考实现代码与注释

[cpp]

intsearchKthInRotatedArray(intA[],intn,intk) { intposMin=searchMinInRotatedArray(A,n); return(posMin+k-1)%n; }

12，查找旋转数组的最小数字

题目：即找分界点，比如3 4 5 1 2，返回的是位置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]

intbSearchMinValue(inta[],intlow,inthigh){ //终止递归条件是low和high差1，原因是后面mid都不是+1-1处理的 if(low+1==high) returnhigh; intmid=(low+high)/2; if(a[mid]>a[low])//左侧有序，在右边找分界点 returnbSearchMinValue(a,mid,high); if(a[mid]//右侧有序，在左边找分界点 returnbSearchMinValue(a,low,mid); return-1; }