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

• 一、题目描述
• 二、解题思路
• • 1. 简单版本
  • 2.优化版本

不动脑子地直接遍历一遍，若相等就计数。

代码如下（示例）：

class Solution {
public:
    int search(vector& nums, int target) {
        int number=0;
        if(nums.size() == 0 || nums[0]>target || nums[nums.size()-1] 
但是结果比较惨淡，时间复杂度为O（n）。
 
 
2.优化版本 
注意到题目说，这是一个非递减数组。嗯，这是一个有序数组，比较好办了，我们可以先使用二分查找，先找到一个数等于target，然后左右两边扫描，计数。最差的结果会遇到这种[1,1,1,1,1,1,1],嗯需要扫描整个数组，那么时间复杂度还是O(n);
 
这里就要说到二分查找的条件了：
 
用于查找的内容逻辑上来说应该是有序的
查找的数量只能是一个，而不是多个
 这样二分查找的时间复杂度才会是 O(logn)
 
我们先来复习一下二分查找怎么写
 
int search(int nums[], int size, int target) //nums是数组，size是数组的大小，target是需要查找的值
{
    int left = 0;
    int right = size - 1;	// 定义了target在左闭右闭的区间内，[left, right]
    while (left <= right) {	//当left == right时，区间[left, right]仍然有效
        int middle = left + ((right - left) / 2);//等同于 (left + right) / 2，防止溢出
        if (nums[middle] > target) {
            right = middle - 1;	//target在左区间，所以[left, middle - 1]
        } else if (nums[middle] < target) {
            left = middle + 1;	//target在右区间，所以[middle + 1, right]
        } else {	//既不在左边，也不在右边，那就是找到答案了
            return middle;
        }
    }
    //没有找到目标值
    return -1;
}

 
上面所说的，表示一般的二分查找在此题中 复杂度还很高。 所以需要改进。因为我们要找的是一个区间，而不是一个数。
 所以，我们只需要找到这个区间的第一个数，和最后一个数就可以了
 以第一个数为例;
 先按照二分查找法找到了一个数，下标为k, 等于target，但是不确定是不是第一个数，
 我们只需要检测，这个数的前面一个数 是不是也等于target,
 若 第k-1个数 =target,则不是第k个数不是第一个数，则继续在左区间找
 若第k-1个数 不等于 target,则就是第一个数，同样的方法再找区间的最后一个数
 
class Solution {
public:
    int search(vector& nums, int target) {
        int number=0;
        int length=nums.size();

        if(length>0)
        {
            int f=searchFirst(nums,0,length-1,target);
            int s=searchSecond(nums,0,length-1,target);
            if(f>-1 && s>-1)
            {
                number=s-f+1;
            }
        }
        return number;
    }
    //找到数组中第一个target的下标，若不存在target，返回-1
    int searchFirst(vector &nums,int start,int end,int k)
    {
        if(start>end)
        {
            return -1;
        }
        int middle=start+(end-start)/2;
        int  middleData=nums[middle];
        if(middleData==k)
        {
            if((middle>0 && nums[middle-1]!=k) || middle==0)
            {
                return middle;
            }
            else
            {
                end=middle-1;
            }
        }
        else if(middleData > k)
        {
            end=middle-1;
        }
        else
        {
            start=middle+1;
        }
        return searchFirst(nums,start,end,k);
    }
//找数组中最后一个k的下标，若不存在，则返回-1
    int searchSecond(vector &nums,int start,int end,int k)
    {
        if(start>end)
        {
            return -1;
        }
        int middle=start+(end-start)/2;
        int  middleData=nums[middle];
        if(middleData==k)
        {
            if((middle 
 
时间复杂度为O(logn)