Total Occurrence of Target

Given a target number and an integer array sorted in ascending order. Find the total number of occurrences of target in the array.

Example

Given[1, 3, 3, 4, 5]and target =3, return2.

Given[2, 2, 3, 4, 6]and target =4, return1.

Given[1, 2, 3, 4, 5]and target =6, return0.

Solution: Binary Search the left bound and right bound.

 public int totalOccurrence(int[] A, int target) {
     if(A == null || A.length == 0) {
         return 0;
     }
     int start = 0, end = A.length - 1;
     boolean isExist = false;
     int leftBound = 0;
     while(start <= end) {
         int mid = start + (end - start) / 2;
         if(A[mid] == target) {
             isExist = true;
         }
         if(A[mid] < target) {
             start = mid + 1;
         }
         else {
             end = mid - 1;
         }
     }
     leftBound = start;

     if(!isExist) {
         return 0;
     }

     int nstart = 0, nend = A.length - 1;
     int rightBound = 0;
     while(nstart <= nend) {
         int mid = nstart + (nend - nstart) / 2;
         if(A[mid] > target) {
             nend = mid - 1;
         }
         else {
             nstart = mid + 1;
         }
     }
     rightBound = nend;

     return rightBound - leftBound + 1;
 }