剑指37-数字在排序数组中出现的次数

二分查找

题目描述

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

解法

思想很简单，用二分法在排序数组中找到该数字的位置，再往两边查找

#include<iostream>
#include<vector>
using namespace std;


class Solution {
public:
    int binarySort(vector<int> data, int k, int left, int right) //二分查找
    {
        if (left > right) return -1;
        int mid = left + (right - left) / 2;
        if (data[mid] == k) return mid;
        if (data[mid] > k) return binarySort(data, k, left, mid - 1);
        if (data[mid] < k) return binarySort(data, k, mid + 1, right);
    }

    int GetNumberOfK(vector<int> data, int k) {
        int res = 0;
        int pos = binarySort(data, k, 0, data.size() - 1);
        cout << pos <<endl;
        if (pos < 0) return res;
        else res = 1;
        int left = pos, right = pos;
        while (right < data.size() && right + 1 < data.size()) //往右相等的个数
        {
            if (data[right + 1] == data[right])
            {
                right++;
                res++;
            }
            else break;
        }

        while (left >= 0 && left - 1 >= 0)  //往左相等的个数
        {
            if (data[left - 1] == data[left])
            {
                left--;
                res++;
            }
            else break;
        }
        return res;
    }
};

//void main() 
//{
//    vector<int> data = { 1,2,3,4,5,6,7 };
//    Solution s;
//    cout<< s.GetNumberOfK(data, 3);
//
//}