[LintCode] 462 Total Occurrence of Target 解题报告

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)

思路
二分法。先找第一个出现的target，再找最后一个出现的target。

Code

public class Solution {
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    public int totalOccurrence(int[] A, int target) {
        // Write your code here
        
        if (A == null || A.length == 0) {
            return 0;
        }

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

        int firstIndex = 0;
        if (A[start] == target) {
            firstIndex = start;
        }
        else if (A[end] == target) {
            firstIndex = end;
        }
        else {
            return 0;
        }
        
        start = 0;
        end = A.length - 1;
        
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] <= target) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        
        int lastIndex = 0;
        if (A[end] == target) {
            lastIndex = end;
        }
        else {
            lastIndex = start;
        }
        
        return lastIndex - firstIndex + 1;

    }
}