剑指Offer-在排序数组中查找数字

📝题目

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
 

限制：
· 0 <= 数组长度 <= 50000

📝思路

O(N)的做法人人都会，但对于一个排序数组而言，二分查找显然是能够有效降低时间复杂度的捷径。
利用二分法，找到target第一次出现和最后一次出现的位置，详细题解可参考《剑指Offer》第6.3节。
注意数组为空的情况。

📝题解

int getFirst(vector<int>& nums, int target, int left, int right) {
    if (left > right)   return -1;
    int mid = (right + left) / 2;
    if (nums[mid] == target) {
        if (mid == 0 || mid > 0 && nums[mid-1] != target) {
            return mid;
        }
        else return getFirst(nums, target, left, mid - 1);
    }
    else if (nums[mid] > target) {
        return getFirst(nums, target, left, mid - 1);
    }
    else {
        return getFirst(nums, target, mid + 1, right);
    }
}

int getLast(vector<int>& nums, int target, int left, int right) {
    if (left > right)   return -1;
    int mid = (right + left) / 2;
    if (nums[mid] == target) {
        if (mid == nums.size() - 1 || nums[mid+1] != target) {
            return mid;
        }
        else return getLast(nums, target, mid + 1, right);
    }
    else if (nums[mid] > target) {
        return getLast(nums, target, left, mid - 1);
    }
    else {
        return getLast(nums, target, mid + 1, right);
    }
}

int search(vector<int>& nums, int target) {
    if (nums.size() < 1)    return 0;
    int left = getFirst(nums, target, 0, nums.size() - 1);
    int right = getLast(nums, target, 0, nums.size() - 1);
    if (left >= 0 && right >= 0)    return right - left + 1;
    return 0;
}