there is a solved recursion exercise that I don't understand:
Implement the int rsearch(int i, int d, const T& x) method of the vector_t class that performs a recursive binary search on an unordered vector, returning the position of the element found and -1 if not found.
This is the solved exercise:
template<class T>
int vector_t<T>:: rsearch(int i, int d, const T& x){
int c=-1;
if (i<=d){
c=(i+d)/2;
if (v_[c] !=x){
int c1=rsearch(i,c-1,x);
int c2=rsearch(c+1,d,x);
c= max(c1,c2);
}
}
return c;
}
MY DOUBT WITH THIS CODE: why does it do this c= max(c1,c2);
?
These are the classes it makes use of:
template <class T>
class vector_t{
private:
T* v_;
int sz_;
public:
vector_t(int sz);
~vector_t(void);
int get_sz(void) const;
T get_v(int pos) const;
T& get_set_v(int pos);
};
Thank you
If the position of the element found is a positive number or zero
num_positivo
and if it is not found it is-1
themax(-1,num_positivo)=num_positivo
, max is the maximum between two numbersrsearch
It works by calculating the center of the vector, if the value sought is the center, it returns its position, if it does not search recursively with rsearch on the left and rsearch on the right, since the indices of an array are positive, the maximum will always be the value. found if givenThis function forces to execute the search on the right even if it has been found on the left, it would be better like this:
And I personally prefer this style of code:
It's a shorthand way of saying: