统计一个数组在排序数组中出现的次数,C++,二分查找

在排序数组中查找很容易想到的就是二分查找，这样的查找效率是相当高的。

找到之后，再在这个数的周围向左或者向右进行延伸，查找有多少个相同的数字。

这次编程主要遇到的问题就是，对二分查找的要点已经忘得差不多了，所以特意写个博客记录。

这个数组中本身含有想要查找的数字很简单，设定三个值，left，middle，right。如果array【middle】>k，就更新right=middle。类似的查找，可以看下面的代码。

难点在于，数组中并没有想要查找的数字，这时候就要分情况讨论

一、要查找的数字比所有的数字都小

二、要查找的数字比所有的数字都大

三、要查找的数字在范围内，但是却没有这个数字。这时候，根据上面的查找算法，加入说，要查找7这个数字，数组内部是｛6，8｝；这时候

1）array[left] = 6,array[right] = 8;middle = (left + right)/2.所以array[middle]=6(middle 等于 left);

这时候array[middle]<7,按照算法，应该left=middle，但是这样的话就会陷入死循环。所以应该判断当left=middle的时候，不进行赋值，退出；

2）同样是查找7这个数字，但是数组是｛6，8，9｝；

这时候array[middle]=8>7,right赋值为middle，接着陷入之前的境地。

代码如下：

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if (data.size() == 0 || data[0] > k || data[data.size() - 1] < k)
        {
            return 0;
        }
        int left = 0;
        int right = data.size();
        int middle = (left + right)/2;
        while (true)
        {
            if (data[middle] == k)
            {
                break;
                //如果中间数比k还大的话，就应该去小的一部分数字中寻找 
            } else if (data[middle] > k) {
                right = middle;
            } else {
                if (left == middle)
                {
                    return 0;
                }
                left = middle;
            }
            middle = (left + right) /2;
        }
        left = middle - 1;
        right = middle + 1;
        int count = 1;
        while (left >= 0 && data[left--] == k)
        {
            count++;
        }
        while (right < data.size() && data[right++] == k)
        {
            count++;
        }
        return count;
    }
};
int main()
{
    int array[6] = {3,3,3,3,4,5};
    vector<int> vec(array, array + 6);
    cout<<Solution().GetNumberOfK(vec, 3)<<endl;
    return 0;
}