二分查找及其变形
程序员文章站
2022-07-12 09:36:42
...
一、把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
方法一:O(n)
public int minNumberInRotateArray(int [] array) {
int len=array.length;
for(int i=1;i<len;i++){
if(array[i-1]>array[i])
return array[i];
}
return array[0];
}
方法二:O(logn)
public int rotate(int[] array){
int low=0,high=array.length-1;
while(low<=high){
int mid=(low+high)/2;
if(array[mid]<array[high]) //此时不可能在mid以右,因为右边是递增的不可能出现最小值
high=mid;
else if(array[mid]>array[high]) //这个时候肯定在mid和high之间,而且不可能是mid
low=mid+1;
else{
high=high-1; //其它时候无法判断在mid左边还是mid右边,所以逐次缩小 eg:10111 11101
}
}
return array[low];
}
二、给出两个有序数组,求有序数组中出现的共同数字的个数
方法一:暴力求解,遍历A数组每一个数字然后在B数组中遍历寻找
public int CountCommon(int[] A,int[] B){
int cnt=0;
for(int i=0;i<A.length;i++){
for(int j=0;j<B.length;j++){
if(B[j]==A[i]){
cnt++;
break;
}
}
}//
return cnt;
}
方法二:在数组B中寻找时采用二分查找,减少一半时间复杂度
public int CountCommon02(int[] A,int[] B){
int cnt=0;
for(int i=0;i<A.length;i++){
int low=0,high=B.length-1;
while(low<=high){
int mid=(low+high)/2;
if(B[mid]==A[i]){
cnt++;
break;
}
else if(B[mid]<A[i])
low=mid+1;
else
high=mid-1;
}
}
return cnt;
}
方法三:最优解法,A,B数组同时产生两个指针分别移动比较,谁小移动谁,相等一起动(并在此刻计数)
public int CountCommon03(int[] A,int[] B){
int index1=0;
int index2=0;
int cnt=0;
while(index1<A.length&&index2<B.length){
if(A[index1]<B[index2])
index1++;
else if(A[index1]>B[index2])
index2++;
else{
cnt++;
index1++;
index2++;
}
}
return cnt;
}
三、统计一个数字在排序数组中出现的次数。
用二分查找的思想寻找第一次和最后一次的下标,时间复杂度O(logn)
public int GetNumberOfK(int [] array , int k) {
if(array==null) return -1;
if(firstIndex(array,k)>=0&&lastIndex(array,k)>=0)
return lastIndex(array,k)-firstIndex(array,k)+1;
else
return 0;
}
//返回数字k在有序数组中出现的第一次的下标,不存在返回-1
public int firstIndex(int[] array,int k){
int low=0,high=array.length-1;
while(low<=high){
int mid=(low+high)/2;
if(array[mid]<k)
low=mid+1;
else
high=mid-1;
}
if(low>=0&&low<array.length&&array[low]==k) return low;
else return -1;
}
//返回数字k在有序数组中出现的最后一次的下标,不存在返回-1
public int lastIndex(int[] array,int k){
int low=0,high=array.length-1;
while(low<=high){
int mid=(low+high)/2;
if(array[mid]<=k)
low=mid+1;
else
high=mid-1;
}
if(high>=0&&high<array.length&&array[high]==k) return high;
else return -1;
}
public int firstIndex02(int[] array,int k){
int low=0,high=array.length-1;
while(low<=high){
int mid=(low+high)/2;
if(array[mid]<k)
low=mid+1;
else if(array[mid]>k)
high=mid-1;
else{
if(mid==0) return mid;
if(mid>0&&array[mid]==array[mid-1]) high=mid-1;
else return mid;
}
}
return -1;
}
public int lastIndex02(int[] array,int k){
int low=0,high=array.length-1;
while(low<=high){
int mid=(low+high)/2;
if(array[mid]<k)
low=mid+1;
else if(array[mid]>k)
high=mid-1;
else{
if(mid==array.length-1) return mid;
if(mid<array.length-1&&array[mid]==array[mid+1]) low=mid+1;
else return mid;
}
}
return -1;
}