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.

http://www.lintcode.com/en/problem/total-occurrence-of-target/ (ladder only)

Discussion

找到第一次出现的postion，找到最后一次出现的position，中间都是target。用二分查找两次。

Solution

int totalOccurrence(vector<int>& nums, int target) {
        //use binary search for sorted array
        if(nums.empty()) return 0;
        int start = 0;
        int end = nums.size() -1 ;
        //stop searching when start and end are neighboring
        //1. find the first postion targes occurs
        int first_occur = -1;
        while(start + 1 < end) {
            int mid =  start + (end - start) / 2;
            if(nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if(nums[start] == target) {
            first_occur = start;
        } else if(nums[end] == target){
            first_occur = end;
        } else {
            return 0;//no target in the array nums
        }
        //2. find the last position target occurs
        start = first_occur;
        end = nums.size() - 1;
        int last_occur = first_occur;
        while(start + 1 < end) {
            int mid =  start + (end - start) / 2;
            if(nums[mid] <= target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if(nums[end] == target) {
            last_occur = end;
        } else {
            last_occur = start;
        }
        return last_occur - first_occur + 1;
    }
};

O(n) 的笨办法：

int totalOccurrence(vector<int>& nums, int target) {
        int cnt = 0;    
        int i = 0;
        //1. skip numbers before target occurs
        while(i<nums.size() && nums[i] != target) {
            i++;
        }
        while(i<nums.size() && nums[i] == target) {
            cnt++;
            i++;
        }
        return cnt;
    }