Using templates write a function named problem3 that accepts iterators to the be

Question

Using templates write a function named problem3 that accepts iterators to the beginning and
end of a range and an element to search for. The function returns the number
of steps taken if binary search were used to find the element or determine
that it is not present. And runs with test code below.

  int main( int argc, char** argv) {

std::vector<int> bin_vals = {-2, -1, 2, 4, 8};
   if (1 != problem3(bin_vals.begin(), bin_vals.end(), 2) or
           3 != problem3(bin_vals.begin(), bin_vals.end(), 0) or
           2 != problem3(bin_vals.begin(), bin_vals.end(), 8)) {
       std::cerr<<"Test 3 failed ";
   }
   else {
       std::cerr<<"Test 3 passed ";
       score += 15;
   }

}

Explanation / Answer

template<typename T>

T Search( T::iterator begin, T::iterator end , T val) {

T::iterator pos=(begin+end)/2;

int count =0;

T::iterator it = pos;

        while((*it!=val)&&(begin<=end)){

       count++;

       if(*it>val)

       {end=pos-1;}

       else

       {begin=pos+1;}

       pos=(begin+end)/2;

       }

return count;

    }

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.