# Doubt binary search recursive unsorted vector

3

There is a solved recursive exercise that I do not understand:

Implement the method int rsearch (int i, int d, const T & x) of the vector_t class that performs the recursive binary search on an unordered vector, returning the position of the found element and -1 if it does not find it.

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 is this doing `c= max(c1,c2);` ?

these are the classes he uses:

``````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);
};
``````

Thanks

asked by AER 24.07.2017 в 15:28
source

4

If the position of the element found is a positive number or zero `num_positivo` and if it is not found it is `-1` the `max(-1,num_positivo)=num_positivo` , max is the maximum between two numbers

`rsearch` works calculating the center of the vector if the value sought is the center returns the position of this, if it does not look recursively with rsearch to the left and rsearch to the right as the indices of an array are positive the maximum it will always be the value found if it occurs

``````template<class T>
int vector_t<T>:: rsearch(int i, int d, const T& x){
//i es izquierda d derecha y x el valor a buscar c de centro
int c=-1;//valor por defecto

if (i<=d){  // si divides el vector puede que no halla una mitad

c=(i+d)/2;//Toma el elemento del centro de la lista

if (v_[c] !=x){ //Si No es el elemento del centro
int c1=rsearch(i,c-1,x); //Buscar en la lista a la izquierda
int c2=rsearch(c+1,d,x); //Buscar en la lista a la derecha
c= max(c1,c2);// si es mayor que -1 es que encontro el Elemento
}
}

return c;//Si c no fue encontrado devuelve -1 q era el valor original
}
``````

This function forces to execute the search to the right even if it has been found on the left, it would be better this way:

``````template<class T>
int vector_t<T>:: rsearch(int i, int d, const T& x){

int c=-1;//valor por defecto

if (i<=d){  // si divides el vector puede que no halla una mitad

c=(i+d)/2;//Toma el elemento del centro de la lista

if (v_[c] !=x){
c=rsearch(i,c-1,x);
if(c==-1)c=rsearch(c+1,d,x); //Si no lo encontro al la izquierda buscar a la derecha
}
}

return c;
}
``````

And I personally prefer this style of code:

``````template<class T>
int vector_t<T>:: rsearch(int i, int d, const T& x){
if (i>d)return -1; //El indice de la izquierda no puede ser mayor que el de la derecha
int c=(i+d)/2;//El centro de la lista si i==d es 2i/2 ==i==d
if (v_[c] ==x)return c;
c=rsearch(i,c-1,x);
if(c!=-1)return c;
c=rsearch(c+1,d,x);
return c;
}
``````

source
1

It is a short form of saying:

``````if ((c1 == -1) && (c2 == -1)) {
c = -1; // No encontrado en ningún subárbol.
} else {
if (c1 == -1) { // c2 != -1
c = c2;  // Encontrado en el subárbol 2.
} else {  // c1 != -1
c = c1;  // Encontrado en el subárbol 1.
}
}
``````