欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找及其变形

程序员文章站 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;
	}