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

Examples

• A = {1, 2, 3, 4, 5}, T = 3, return 1
• A = {1, 2, 2, 2, 3}, T = 2, return 3
• A = {1, 2, 2, 2, 3}, T = 4, return 0

Corner Cases

• What if A is null? We should return 0 in this case.

Solution: 分别找first occurrence和last occurrence of target

  public int totalOccurrence(int[] array, int target) {
    if (array == null || array.length == 0) {
      return 0;
    }
    int start = 0, end = array.length - 1, head = 0, tail = 0;
    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (array[mid] >= target) {
        end = mid;
      } else {
        start = mid;
      }
    }
    if (array[start] == target) {
      head = start;
    } else if (array[end] == target) {
      head = end;
    } else {
      return 0;
    }
    start = 0; end = array.length - 1;
    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (array[mid] <= target) {
        start = mid;
      } else {
        end = mid;
      }
    }
    if (array[end] == target) {
      tail = end;
    } else if (array[start] == target) {
      tail = start;
    }
    return tail - head + 1;
  }