First occurrence

Go to the Jutge statement of the problem

Write an efficient function int first_occurrence(double x, const vector<double>& v); that returns the position of the first occurrence of x in the vector v. If x does not belong to v, return a -1. Assume the vector v is sorted in non-decreasing order.

Hint

Use the code provided in the Jutge statement. The function to implement is really similar to Dichotomic Search. What is the base case in this context?

A possible C++ code to start the problem

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

int first_occurrence(double x, const vector<double>& v, int left, int right){
    // Similar to dichotomic search
}

int first_occurrence(double x, const vector<double>& v){
    return first_occurrence(x, v, 0, v.size()-1);
}


int main() {
    int n;
    while (cin >> n) {
        vector<double> V(n);
        for (int i = 0; i < n; ++i) cin >> V[i];
        int t;
        cin >> t;
        while (t--) {
            double x;
            cin >> x;
            cout << first_occurrence(x, V) << endl;
        }
    }
}

A possible solution

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

int first_occurrence(double x, const vector<double>& v, int left, int right){
    //base case
    if (left > right) return -1;
    if (left == right) return (v[left] == x) ? left : -1 ;
    int mid = (left+right)/2;
    if (v[mid] >= x) return first_occurrence(x, v, left, mid); 
    if (v[mid] < x) return first_occurrence(x, v, mid+1, right);
}

int first_occurrence(double x, const vector<double>& v){
    return first_occurrence(x, v, 0, v.size()-1);
}


int main() {
    int n;
    while (cin >> n) {
        vector<double> V(n);
        for (int i = 0; i < n; ++i) cin >> V[i];
        int t;
        cin >> t;
        while (t--) {
            double x;
            cin >> x;
            cout << first_occurrence(x, V) << endl;
        }
    }
}