4/22剑指offer

1.在排序数组中查找数字
（1）数字在排序数组中出现的次数
给一个排序数组，一个数字，查找这个数字出现的次数。要求ologn。
思路：利用二分查找算法，分别确定重复出现的第一个k和最后一个k。

int GetFirstK(int *data,int length,int k,int start,int end)
{
    if(start>end)
        return -1;//没找到
    int middleIndex=(start+end)/2;
    int middleData=data[middleIndex];
    if(middleData==k)
    {
        if(middleIndex>0&&data[middleIndex-1]!=k||middleIndex==0)
              return middleIndex;//是第一个k的条件，前面没有等于k的了，或它下标为0
        else
              end=middleIndex-1;//第一k在前面半段
    }
    else if(middleIndex>k)
    {
        end=middleIndex-1;//第一个k在前面半段
    }
    else
    {
        start=middleIndex+1;//第一个k在后面半段
    }
    return GetFirstK(data,length,k,start,end);
}
int GetLastK(int *data,int length,int k,int start,int end)
{
    if(start>end)
        return -1;
    int middleIndex=(start+end)/2;
    int middleData=data[middleIndex];
    if(middleData==k)
    {
        if(middleIndex<length-1&&data[middleIndex+1]!=k||middleIndex==length-1)
              return middleIndex;//是最后一个k的条件，后面没有k了，或者其下标是最后一个
        else
              start=middleIndex+1;//最后一个k在后面半段
    }
    else if(middleIndex<k)
    {
        start=middleIndex+1;//最后一个k在后面半段
    }
    else
    {
        start=middleIndex-1;//最后一个k在前面半段
    }
    return GetFirstK(data,length,k,start,end);
}
int GetNumberOfK(int*data,int length,int k)
{
    int number=0;
    if(data!=nullptr&&length>0)
    {
        int first=GetFirstK(data,length,k,0,length-1);
        int last=GetLastK(data,length,k,0,length-1);
        if(first>-1&&last>-1)
        number=last-first+1；
    }
    return number;
}

（2）0到n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0-n-1之内。在范围0-n-1内的n个数字中有且只有一个数字不在该数组中，找出这个数字。
思路一：两个数列求和找差。
思路二：问题可以转换为在排序数组中找出第一个值和下标不相等的元素，因为一共只缺少一个数字，此数字前面的数字应该等于他们的下标，而此数字后面的数字都等于他们的下标+1.

int GetMissingNumber(const int* numbers,int length)
{
    if(numbers==nullptr||length<=0)
      return -1;
    int left=0;
    int right=length-1;
    while(left<=right)
    {
        int middle=(right-left)<<1;
        if(numbers[middle]!=middle)
        {
            if(middle==0||numbers[middle-1]==middle-1)
            {
                return middle;//前面的值都等于其下标，那么这个middle就是缺失的数字
            }
            right=middle-1;//否则，缺失的数字在前面
        }
        else
        {
            left=middle+1;//缺失的数字在后面
        }
    }
    if(left=length)
    {
        return length;
    }
    //无效的输入，比如不是排序数组，或有数字不在0-n-1范围内
    return -1;
}