Description

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, return 2.

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

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

Challenge

Time complexity in O(logn)

4/26/2017

算法班

找左右边界，第一个边界找不出来时候返回0

1 public class Solution { 2     /** 3      * @param A an integer array sorted in ascending order 4      * @param target an integer 5      * @return an integer 6      */ 7     public int totalOccurrence(int[] A, int target) { 8         if (A == null || A.length == 0) return 0; 9         int left, right;10 11         int start = 0, end = A.length - 1;12         while (start + 1 < end) {13             int mid = start + (end - start) / 2;14             if (A[mid] >= target) {15                 end = mid;16             } else {17                 start = mid;18             }19         }20         if (A[start] == target) {21             left = start;22         } else if (A[end] == target) {23             left = end;24         } else {25             return 0;26         }27 28         start = left;29         end = A.length - 1;30         while (start + 1 < end) {31             int mid = start + (end - start) / 2;32             if (A[mid] <= target) {33                 start = mid;34             } else {35                 end = mid;36             }37         }38 39         if (A[end] == target) {40             right = end;41         } else if (A[start] == target) {42             right = start;43         } else {    // shouldn't come to this branch44             return 0;45         }46         return right - left + 1;47     }48 }