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

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

剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（LeetCode） (leetcode-cn.com)

首先放上运行结果

思路

所有的查找都是二分查找。首先查找到一个target出现的位置，然后再在这个位置之前找到target首次出现的位置的前一个位置，然后再在这个位置之后找到target最后一次出现的位置，两个位置之差即为target出现的总次数。

代码

class Solution {
public:
    int search(vector& nums, int target) {
        int beg = 0, end = nums.size(), mid;
        while ((mid = beg + (end - beg) / 2) != end) {
            if (nums[mid] > target) end = mid;
            else if (nums[mid] < target) beg = mid + 1;
            else return get_end(nums, beg, end, target) - get_front(nums, beg, end, target);
        }
        return 0;
    }

    int get_front(vector& nums, int beg, int end, int target) {
        if (nums[beg] == target) return beg - 1;
        int mid, halfsize;
        while (halfsize = (end - beg) / 2) {
            mid = beg + halfsize;
            nums[mid] != target ? beg = mid : end = mid;
        }
        return beg;
    }

    int get_end(vector& nums, int beg, int end, int target) {
        int mid, halfsize;
        while (halfsize = (end - beg) / 2) {
            mid = beg + halfsize;
            nums[mid] == target ? beg = mid : end = mid;
        }
        return beg;
    }
};