Doubt binary search recursive unsorted vector

Question

Doubt binary search recursive unsorted vector

Navigation

#1 by (4 votes)
#2 by (1 votes)

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

c++

asked by AER 24.07.2017 в 15:28

source

2 answers

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.
  }
}

answered by 24.07.2017 в 15:43

Operator test in a conditional Keep the data when going from one select to another

score 4 · Accepted Answer

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