Sword finger offer: the number of times a number appears in a sorted array

Title Description:

The number of times a number appears in a sorted array

Thoughts:

The improvement of binary search finds the number k in the array for the first time and the last time start,end, and the final time is end start + 1

Two variables, start and end, are defined, which means to traverse from start to end, find the middle position mid of start and end, and compare the size of mid and k. there are three situations:

a[mid] == k : 

If it is to find the location of the first occurrence, and the previous number of mid is not k, then mid is the location of the first occurrence of K, otherwise it will be found in start-mid-1

If you are looking for the location of the last occurrence, and the number after the mid is not k, then the mid is the location of the last occurrence of K. otherwise, look for the location from mid+1 to end

a[mid]  <   k :   

If you are looking for the first location, start = mid+1

If you are looking for the last location, start = mid+1

a[mid]  >   k :

If you are looking for the first location, end= mid-1

If you are looking for the last location, end= mid-1

Code implementation:

/**
	 * Find out the number of the first and last occurrence of k respectively, and improve the binary search
	 */
	 public int GetNumberOfK(int [] array , int k) {
		 int first=0,last=0,number=0;
		 if(array != null && array.length > 0){
			 first = getFirstK(array,k,0,array.length-1);
			 last = getLastK(array,k,0,array.length-1);
			 
			 if(first > -1 && last > -1){
				 number = last-first+1;
			 }
		 }
		 return number;
	 }
	 
	 private int getLastK(int[] array, int k, int start, int end) {
		 if(start > end){
				return -1;
		 }
		 int mid = (end+start)/2;
		 int midata = array[mid];
		 if(midata == k){
			 if((mid<array.length-1 && array[mid+1]!=k) || mid==end){
				 return mid;
			 }else{
				 start = mid+1;
			 }
		 }else if(midata > k){
			 end = mid-1;
		 }else{
			 start = mid+1;
		 }
		return getLastK(array,k,start,end);
	}
	private int getFirstK(int[] array, int k, int start, int end) {
		if(start > end){
			return -1;
		}
		int mid = (end+start)/2;
		int midata = array[mid];
//		midata is divided into three situations = = ><
		if(midata == k){
//			Is it the first
			if((mid>0 && array[mid-1]!=k) || mid==0){
				return mid;
			}else{
				end = mid-1;
			}
		}else if(midata > k){
			end = mid-1;
		}else{
			start = mid+1;
		}
		return getFirstK(array,k,start,end);
	}

Test code:

@Test
	 public void test1(){
		 int[] a = {1,3,5,7,7,7};
		 System.out.println(GetNumberOfK(a,7));
	 }

Test results:



Posted on Thu, 13 Feb 2020 11:16:52 -0800 by sangoku