面试题53(1):在排序数组中查找数字

题目

数字在排序数组中出现的次数
统计一个数字在排序树组中出现的次数。例如.输入排序树组{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4

解题思路

1)采用二分查找算法，其时间复杂度为O(logn)。

2. 找出数组中间的数字sorted_array[mid]和数字k作比较
   a) sorted_array[mid] > k时，k只可能出现在数组的前半段，那么下一轮只用在数组的前半段查找 right= mid-1。
   b) sorted_array[mid] < k时，k只可能出现在数组的后半段，那么下一轮只用在数组的后半段查找 left = mid+1
   c) sorted_array[mid] = k时，先判断这个数字是不是第一个k。
   若中间数字的前一个数字不是k，那么此时中间数字刚好就是第一个k,(sorted_array[mid-1] != k)。
   若中间数字的前一个数字也是k，那么第一个k肯定出现在数组的前半段(right = mid-1)，那么下一轮仍然需要在数组的前半段查找。

代码

class Solution{
  public:
    int getFirstk(int *sorted_array,int left,int right,int k)
    {
        if(left <= right)
        {
            int index = (left + right) >> 1;
            int mid   = sorted_array[index];

            if(k < mid)
            {
                right = index - 1;
            }
            else if(k > mid)
            {
                left  = index + 1;
            }
            else
            {
                if((index == 0) || (index > 0 && sorted_array[index-1]!= k))
                {
                    return index;
                }
                else
                {
                    right = index -1;
                }
            }
            return getFirstk(sorted_array,left,right,k);
        }
        else
        {
            return -1;
        }
    }
    
    int getLastk(int *sorted_array,int length,int left,int right,int k)
    {
        if(left <= right)
        {
            int index = (left + right) >> 1;
            int mid   = sorted_array[index];

            if(k<mid)
            {
                right = index - 1;
            }
            else if(k > mid)
            {
                left  = index + 1;
            }
            else{
                if((index == length) || (index < length && sorted_array[index+1]!=k))
                {
                    return index;
                }
                else
                {
                    left = index +1;
                }
            }
            return getLastk(sorted_array,length,left,right,k);
        }
        else{
            return -1;    
        }
    }

    int getNumberk(int *sorted_array,int length,int k)
    {
        if(length == 0)
        {
            return 0;
        }
        int first = 0;
        int last  = 0;
        first = getFirstk(sorted_array,0,length-1,k);
        last  = getLastk(sorted_array,length-1,0,length-1,k);

        if(first != -1 && last != -1)
        {
            return last-first+1;
        }
        return 0;
    }
    
};

完整代码见Github