[이진 탐색] 정렬된 배열에서 특정 수의 개수 구하기 ★★☆

기출 : Zoho 인터뷰

 

C++ STL의 upper_bound, lower_bound의 개념에 대해 새로 알았다

 

직접 작성한 코드와 STL을 사용한 코드 모두 올렸다

#include<bits/stdc++.h>
using namespace std;
int n, x, ans;
vector<int> v;

int lowerbound(int st, int en, int target) {
    if (st > en) return -1;
    int mid = (st + en) / 2;
    if ((mid == 0 || v[mid - 1] < target) && v[mid] == target) return mid;
    if (v[mid] >= target) lowerbound(st, mid-1, target);
    else lowerbound(mid+1, en, target);
}

int upperbound(int st, int en, int target) {
    if (st > en) return -1;
    int mid = (st + en) / 2;
    if ((mid == n - 1 || v[mid + 1] > target) && v[mid] == target) return mid;
    if (v[mid] <= target) upperbound(mid + 1, en, target);
    else upperbound(st, mid - 1, target);

}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> x;
    for (int i = 0;i < n;i++) {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    int lb = lowerbound(0, n - 1, x);
    int ub = upperbound(0, n - 1, x);
    if (lb != -1) {
        cout << ub - lb + 1;
        return 0;
    }
    cout << -1;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n, x, ans;
vector<int> v;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> x;
    for (int i = 0;i < n;i++) {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    vector<int>::iterator lb = lower_bound(v.begin(), v.end(), x);
    vector<int>::iterator ub = upper_bound(v.begin(), v.end(), x);
    int cnt = ub - lb;
    if (cnt == 0) cout << -1;
    else cout << cnt;
    return 0;
}