作者：whisper

链接：https://www.proprogrammar.com/article/879

声明：请尊重原作者的劳动，如需转载请注明出处

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

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

示例 1:

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

示例 2:

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

难度：简单；标签：数组，二分查找；编程语言：C++

我的解法

class Solution {
public:
    //c++重写,logn复杂度
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, mid = -1;
        
        if(nums.size() == 0){
            return 0;
        }
        
        while(right >= left){
            mid = (right + left) / 2;
            if(nums[mid] == target){
                break;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        
        int left2, right2, mid2 = -1;
        if(nums[mid] == target){
            right2 = right;
            left2 = mid;
            right = mid;
            
            while(right2 >= left2){
                mid2 = (right2 + left2) / 2;
                if(nums[mid2] > target){
                    right2 = mid2 - 1;
                }else{
                    left2 = mid2 + 1;
                }
            }
            
            while(right >= left){
                mid = (right + left) / 2;
                if(nums[mid] < target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }else{
            return 0;
        }
        
        return (nums[mid2] > target ? mid2 - 1 : mid2) - (nums[mid] < target ? mid + 1 : mid) + 1;
    }
};

这里先二分查找找到一个target的位置，然后这个target位置的左右可能还有值为target的数，再左右二分查找target，最后mid, mid2就在target值的左，右边界附近了，注意return值要处理一下

其它解法

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int i=0, j=nums.size()-1;
        while(i<j){
            int mididx = (i+j)/2;
            //printf("%d,%d,%d\n", i, j, mididx);
            int midnum = nums[mididx];
            if(midnum > target){
                if(mididx == j){
                    j-=1;
                    continue;
                }
                j = mididx;
            }else if(midnum < target){
                if(mididx == i){
                    i+=1;
                    continue;
                }
                i = mididx;
            }else if(nums[i] < target){
                i++;
            }else if(nums[j]>target){
                j--;
            }else{
                break;
            }
        }
        //printf("i:%d,j:%d\n", i, j);
        if(j==i && nums[i]!=target)
        {
            return 0;
        }
        int ret = j-i+1;
        return ret;
    }
};

上面的意思是先二分找值为target的数，找到后左右指针每次+1，-1（不再二分）向找到的值target的数靠近，直到左，右（i, j）位置的数值都是target，如果中间有数不为target，再次二分，为target，再+1, -1，如此反复

亲爱的读者：有时间可以点赞评论一下