Resistant dichotomic search

Go to the Jutge statement of the problem

Write an efficient function bool resistant_search(double x, const vector<double>& v); that tells if x belongs to the vector v or not. Assume the vector v is almost sorted in nondecreasing order, in the sense that there may be at most a pair of indices i and j such that 0 \leq i < j < n and v[i] > v[j].

Hint

This is similar to Problem 2.12 from problem class P3. Use the fact that there is at most 1 inversion, i.e. a pair of indices i<j such that v[i]>v[j].

A possible C++ code to start the problem

#include <iostream>
#include <vector>

using namespace std;

bool resistant_search(double x, const vector<double>& v, int left, int right){
    if (left > right)  // i.e. if v has <=0 elements
        return false;
    if(left+1 >= right)  // i.e. if v has <=2 elements
        return x==v[left] or x==v[right];
    int mid = (left + right)/2;
    if (v[mid] > x) 
        // where do we search recursively?
    else if (v[mid] < x) 
        // where do we search recursively?
    else return true;
}

bool resistant_search(double x, const vector<double>& v){
    return resistant_search (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 << resistant_search(x, V) << endl;
        }
    }
}

A possible solution

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

bool resistant_search(double x, const vector<double>& v, int left, int right){
    if (left > right) // i.e. if v has <= 0 elements
        return false;
    if(left+1 >= right) // i.e. if v has <=2 elements
        return x==v[left] or x==v[right];
    int mid = (left + right)/2;
    if (v[mid] > x) 
        return v[mid+1] == x or resistant_search (x, v, left , mid-1); 
    else if (v[mid] < x) 
        return v[mid-1] == x or resistant_search (x, v, mid+1, right); 
    else return true;
}

bool resistant_search(double x, const vector<double>& v){
    return resistant_search (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 << resistant_search(x, V) << endl;
        }
    }
}