在排序数组中,找出给定数字的出现次数

时间:2020-12-26 11:05:34
在排序数组中,找出给定数字的出现次数,比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。

算法:借鉴了stl里面的equal_range算法,关键是处理好边界,二分问题


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

int low(vector<int> &ivec, int left, int right, int x)
{
while(left < right)
{
int mid = (left + right) / 2;
if(ivec[mid] < x)
left = mid + 1;
else
right = mid;
}
return left;
}

int upper(vector<int> &ivec, int left, int right, int x)
{
while(left < right)
{
int mid = (left + right) / 2;
if(ivec[mid] > x)
right = mid;
else
left = mid + 1;
}
return right;
}

int main()
{
clock_t begin = clock();
int n, x, left, right, first = 0, last = 0;
vector<int> ivec;
ifstream infile("input2.txt");
while(infile >> n)
ivec.push_back(n);
cout << "Input x: " << endl;
cin >> x;
left = 0;
right = ivec.size();
while(left < right)
{
int mid = (left + right) / 2;
if(ivec[mid] < x)
left = mid + 1;
else if(ivec[mid] > x)
right = mid + 1;
else
{
first = low(ivec, left, right, x);
cout << first << endl;
last = upper(ivec, left, right, x);
break;
}
}
cout << "Numbers: " << last - first << endl;
clock_t endtime = clock();
cout << "Time: " << (double)(endtime - begin) << endl;
}